3-colouring \(P_t\)-free graphs without short odd cycles
From MaRDI portal
Publication:2696271
DOI10.1007/s00453-022-01049-0OpenAlexW4306655159MaRDI QIDQ2696271
Alberto Rojas Anríquez, Maya Jakobine Stein
Publication date: 11 April 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2008.04845
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity of coloring graphs without paths and cycles
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- The ellipsoid method and its consequences in combinatorial optimization
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Three complexity results on coloring \(P_k\)-free graphs
- Colouring \((P_r + P_s)\)-free graphs
- Better 3-coloring algorithms: excluding a triangle and a seven vertex path
- List coloring in the absence of a linear forest
- Coloring graphs without short cycles and long induced paths
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- The NP-Completeness of Edge-Coloring
- 3-Colorable Subclasses of $P_8$-Free Graphs
- NP completeness of finding the chromatic index of regular graphs
- Reducibility among Combinatorial Problems
This page was built for publication: 3-colouring \(P_t\)-free graphs without short odd cycles
