Some Results on Critical (P5,H)-free Graphs
Xia Wen, Jorik Jooken, Jan Goedgebeur, Shenwei Huang · Theoretical Computer Science · 2025
Given two graphs H 1 and H 2 , a graph is ( H 1 , H 2 ) -free if it contains no induced subgraph isomorphic to H 1 or H 2 . A graph G is k -vertex-critical if every proper induced subgraph of G has chromatic number less than k , but G has chromatic number k . The study of k -vertex-critical graphs for specific 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 exists a polynomial-time certifying algorithm to decide the k -colorability of a graph in the class. In this paper, we show that: (1) for k ≥ 1 , there are finitely many k -vertex-critical ( P 5 , K 1 , 4 + P 1 ) -free graphs; (2) for s ≥ 1 , there are finitely many 5-vertex-critical ( P 5 , K 1 , s + P 1 ) -free graphs; (3) for k ≥ 1 , there are finitely many k -vertex-critical ( P 5 , K 3 + 2 P 1 ‾ ) -free graphs. Moreover, we characterize all 5-vertex-critical ( P 5 , H ) -free graphs where H ∈ { K 1 , 3 + P 1 , K 1 , 4 + P 1 , K 3 + 2 P 1 ‾ } using an exhaustive graph generation algorithm.