On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs

DOI10.1016/j.dam.2016.05.018zbMath1350.05032arXiv1403.8027OpenAlexW2429536804MaRDI QIDQ344847

Tyler J. D. McConnell, Stefan A. Panait, Chính T. Hoàng, Frédéric Maffray, Harjinder S. Dhaliwal, Angèle M. Hamel

Publication date: 24 November 2016

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

Full work available at URL: https://arxiv.org/abs/1403.8027

zbMATH Keywords

graph coloring\(P_5\)-free graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (11)

Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four ⋮ 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 ⋮ 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 ⋮ Critical vertices and edges in \(H\)-free graphs ⋮ Critical \((P_6, \mathrm{banner})\)-free graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs

Cites Work

• Unnamed Item
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• Mathematics and Computer Science: Coping with Finiteness
• A Note on k-Colorability of P 5-Free Graphs
• A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
• Four classes of perfectly orderable graphs
• On $3$-Colorable $P_5$-Free Graphs

This page was built for publication: On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs