Critical \((P_5,dart)\) -Free Graphs

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\) nor \(H_2\) . A dart is the graph obtained from a diamond by adding a new vertex and making it adjacent to exactly one vertex with degree 3 in the diamond. In this paper, we show that there are finitely many k-vertex-critical \((P_5,dart)\) -free graphs for \(k \ge 1\) . To prove these results, we use induction on k and perform a careful structural analysis via Strong Perfect Graph Theorem combined with the pigeonhole principle based on the properties of vertex-critical graphs. Moreover, for \(k \in \{5, 6, 7\}\) we characterize all k-vertex-critical \((P_5,dart)\) -free graphs using a computer generation algorithm. Our results imply the existence of a polynomial-time certifying algorithm to decide the k-colorability of \((P_5,dart)\) -free graphs for \(k \ge 1\) where the certificate is either a k-coloring or a \((k+1)\) -vertex-critical induced subgraph.