On color-critical (P₅,co-P₅)-free graphs

DOI10.1016/J.DAM.2016.05.018MaRDI QIDQ344847zbMATH OpenOpenAlexFDO

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

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)

Abstract: A graph is $k$-critical if it is $k$-chromatic but each of its proper induced subgraphs is ($k-1$)-colorable. It is known that the number of $4$-critical $P_5$-free graphs is finite, but there is an infinite number of $k$-critical $P_5$-free graphs for each $kgeq5$. We show that the number of $k$-critical $(P_5,overline{P}_5)$-free graphs is finite for every fixed $k$. Our result implies the existence of a certifying algorithm for $k$-coloring $(P_5,overline{P}_5)$-free graphs.

Recommendations

• On 3-colorable \(P_5\)-free graphs
• A Note on k-Colorability of P 5-Free Graphs
• On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• Some results on \(k\)-critical \(P_5\)-free graphs
• On the chromatic number of some \(P_5\)-free graphs
• Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors
• On the chromatic number of \((P_{5},K_{2,t})\)-free graphs
• \(k\)-critical graphs in \(P_5\)-free graphs

Cites work

• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A Note on k-Colorability of P 5-Free Graphs
• A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Four classes of perfectly orderable graphs
• Mathematics and computer science: coping with finiteness
• On 3-colorable \(P_5\)-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
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs

Cited in

(17)

• Critical (\(P_5\), bull)-free graphs
• Vertex-critical \((P_5, \mathrm{chair})\)-free graphs
• A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
• \(k\)-critical graphs in \(P_5\)-free graphs
• Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four
• Exhaustive generation of \(k\)-critical \(\mathcal{H}\)-free graphs
• Critical \((P_5,\mathit{dart})\)-free graphs
• Constructions of \(k\)-critical \(P_5\)-free graphs
• On cd-coloring of \(\{P_5,K_4\}\)-free chordal graphs
• Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs
• A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs
• Critical \((P_6, \mathrm{banner})\)-free graphs
• Some results on \(k\)-critical \(P_5\)-free graphs
• \(k\)-critical graphs in \(P_5\)-free graphs
• Critical vertices and edges in \(H\)-free graphs
• Non-perfect \((P_5, C_5, K_5 -e)\)-free graphs are 5-colorable
• Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344847)