On the complexity of 4-coloring graphs without long induced paths
From MaRDI portal
Publication:2465649
DOI10.1016/j.tcs.2007.09.009zbMath1143.68060MaRDI QIDQ2465649
Van Bang Le, Ingo Schiermeyer, Bert Randerath
Publication date: 7 January 2008
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.09.009
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time, On the parameterized complexity of coloring graphs in the absence of a linear forest, Updating the complexity status of coloring graphs without a fixed induced linear forest, Colouring vertices of triangle-free graphs without forests, Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time, 4-Coloring H-Free Graphs When H Is Small, Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs, Colouring Vertices of Triangle-Free Graphs, List Coloring in the Absence of a Linear Forest, A Note on k-Colorability of P 5-Free Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The strong perfect graph theorem
- Some results on graphs without long induced paths
- Dominating cliques in \(P_ 5\)-free graphs
- Geometric algorithms and combinatorial optimization.
- Perfect graphs with no \(P_ 5\) and no \(K_ 5\)
- Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Three-colourability and forbidden subgraphs. II: Polynomial algorithms
- Vertex colouring and forbidden subgraphs -- a survey
- Recognizing Berge graphs