Some Results on k-Critical P_5-Free Graphs
share
A graph G is k-vertex-critical if G has chromatic number k but every proper induced subgraph of G has chromatic number less than k. The study of k-vertex-critical graphs for graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph class is finite, then there is a polynomial-time algorithm to decide if a graph in the class is (k-1)-colorable. In this paper, we prove that for every fixed integer k≥ 1, there are only finitely many k-vertex-critical (P_5,gem)-free graphs and (P_5,P_3+P_2)-free graphs. To prove the results we use a known structure theorem for (P_5,gem)-free graphs combined with properties of k-vertex-critical graphs. Moreover, we characterize all k-vertex-critical (P_5,gem)-free graphs and (P_5,P_3+P_2)-free graphs for k ∈{4,5} using a computer generation algorithm.
READ FULL TEXT