On the complexity of 4-coloring graphs without long induced paths

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

zbMATH Keywords

computational complexity; graph coloring; induced path; \(P_{5}\)-free graph

Mathematics Subject Classification ID

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, Constructions of \(k\)-critical \(P_5\)-free graphs, List coloring in the absence of a linear forest, Coloring graphs without short cycles and long induced paths, 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