%0 Journal Article
%T On color-critical ($P_{5},\overline{P}_5$)-free graphs
%A Harjinder S. Dhaliwal
%A Ang¨¨le M. Hamel
%A Ch¨ªnh T. Ho¨¤ng
%A Fr¨¦d¨¦ric Maffray
%A Tyler J. D. McConnell
%A Stefan A. Panait
%J Mathematics
%D 2014
%I arXiv
%X 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 $k \geq 5$. 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.
%U http://arxiv.org/abs/1403.8027v2