Constructions of \(k\)-critical \(P_5\)-free graphs

DOI10.1016/j.dam.2014.06.007zbMath1306.05061OpenAlexW1989358594MaRDI QIDQ2255047

Yanyan Li

Publication date: 6 February 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.06.007

zbMATH Keywords

graph coloringcritical graphs\(P_5\)-free graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items

Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four ⋮ Dynamic \(F\)-free coloring of graphs ⋮ Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs ⋮ Complexity of coloring graphs without paths and cycles ⋮ 4-coloring \((P_6, \text{bull})\)-free graphs ⋮ Certifying coloring algorithms for graphs without long induced paths ⋮ A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs ⋮ Vertex-critical \((P_5, \mathrm{chair})\)-free graphs ⋮ Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs ⋮ Strengthening Brooks' chromatic bound on \(P_6\)-free graphs ⋮ Critical (\(P_5\), bull)-free graphs ⋮ Some results on \(k\)-critical \(P_5\)-free graphs ⋮ Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs ⋮ Computational aspects of greedy partitioning of graphs ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Better 3-coloring algorithms: excluding a triangle and a seven vertex path ⋮ Critical vertices and edges in \(H\)-free graphs ⋮ Critical \((P_6, \mathrm{banner})\)-free graphs ⋮ Obstructions for three-coloring graphs without induced paths on six vertices ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The strong perfect graph theorem
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Three complexity results on coloring \(P_k\)-free graphs
• On the complexity of 4-coloring graphs without long induced paths
• A Note on k-Colorability of P 5-Free Graphs
• A Certifying Algorithm for 3-Colorability of P 5-Free Graphs

This page was built for publication: Constructions of \(k\)-critical \(P_5\)-free graphs