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

DOI10.1016/J.DAM.2016.05.018zbMATH Open1350.05032arXiv1403.8027OpenAlexW2429536804MaRDI QIDQ344847FDOQ344847

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)

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.

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

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

zbMATH Keywords

graph coloring\(P_5\)-free graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Title not available (Why is that?)
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• Four classes of perfectly orderable graphs
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
• 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
• On $3$-Colorable $P_5$-Free Graphs

Cited In (14)

• \(k\)-critical graphs in \(P_5\)-free graphs
• Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four
• Vertex-critical \((P_5, \mathrm{chair})\)-free graphs
• A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs
• Critical vertices and edges in \(H\)-free graphs
• Critical \((P_5,\mathit{dart})\)-free graphs
• Critical \((P_6, \mathrm{banner})\)-free graphs
• \(k\)-critical graphs in \(P_5\)-free graphs
• On cd-coloring of \(\{P_5,K_4\}\)-free chordal graphs
• Some results on \(k\)-critical \(P_5\)-free graphs
• Critical (\(P_5\), bull)-free graphs
• Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs
• A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
• Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-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)