On color-critical ($P_5,{\overline{P}}_5$)-free graphs

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 $k\ge 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.

13 pages, minor revisions made

Cited by in corpus (1)

• A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs