2021/08/12 by Cai, Qingqiong, Goedgebeur, Jan, Huang, Shenwei
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2108.05492
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 (P5,gem)-free graphs and (P5,P3+P2)-free graphs. To prove the results we use a known structure theorem for (P5,gem)-free graphs combined with properties of k-vertex-critical graphs. Moreover, we characterize all k-vertex-critical (P5,gem)-free graphs and (P5,P3+P2)-free graphs for k ∈ \4,5\ using a computer generation algorithm.