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

DOI10.1016/j.tcs.2007.09.009zbMath1143.68060OpenAlexW2160153943MaRDI QIDQ2465649

Bert Randerath, Ingo Schiermeyer, Van Bang Le

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 complexitygraph coloringinduced path\(P_{5}\)-free graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (20)

4-Coloring H-Free Graphs When H Is Small ⋮ Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time ⋮ Complexity of coloring graphs without paths and cycles ⋮ Colouring \((P_r + P_s)\)-free graphs ⋮ Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time ⋮ Coloring graphs without short cycles and long induced paths ⋮ 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ On the parameterized complexity of coloring graphs in the absence of a linear forest ⋮ Improved complexity results on \(k\)-coloring \(P_t\)-free graphs ⋮ Two complexity results for the vertex coloring problem ⋮ Constructions of \(k\)-critical \(P_5\)-free graphs ⋮ List coloring in the absence of a linear forest ⋮ A Note on k-Colorability of P 5-Free Graphs ⋮ Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs ⋮ Colouring Vertices of Triangle-Free Graphs ⋮ Colouring (P_r+P_s)-Free Graphs ⋮ Updating the complexity status of coloring graphs without a fixed induced linear forest ⋮ Colouring vertices of triangle-free graphs without forests ⋮ List Coloring in the Absence of a Linear Forest

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

This page was built for publication: On the complexity of 4-coloring graphs without long induced paths