Proves finiteness of k-vertex-critical (P5,chair)-free and (P5,cricket)-free graphs for every k, with characterizations for k=5 and k=6, plus algorithmic consequences.
Structural description of (bull, house)-free graphs
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
The bull is a graph consisting of a triangle and two pendant edges. The P_5 is the chordless path on five vertices. The house is the complement of a P_5. 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 k-critical P_5-free graphs and bull-free graphs are infinite for large enough k. We give a structural description of (bull, house)-free graphs and also (bull, P_5)-free graphs. Using these structural properties we prove that for any fixed k, the number of k-critical (bull, P_5)-free graphs is finite. This improves on a result of Huang, Li and Xia (Critical (P_5, bull)-free graphs, Discrete Applied Mathematics 334 (2023) 15-25). A graph G is perfectly divisible if for each induced subgraph H of G with at least one edge, V(H) can be partitioned into two sets V_1, V_2 such that every largest clique of H contains a vertex in V_i for i = 1,2. Chudnovsky and Sivaraman proved that (P_5, bull)-free graphs are perfectly divisible (Perfect divisibility and 2-divisibility, Journal of Graph Theory 90 (2019) 54-60). Our structural result allows us to give a short proof of this theorem.
fields
math.CO 2years
2026 2verdicts
UNVERDICTED 2representative citing papers
There are finitely many k-vertex-critical (co-gem, house)-free graphs and (co-gem, dart)-free graphs for every k ≥ 1.
citing papers explorer
-
Vertex-critical $(P_5,\text{chair})$-free and $(P_5,\text{cricket})$-free graphs
Proves finiteness of k-vertex-critical (P5,chair)-free and (P5,cricket)-free graphs for every k, with characterizations for k=5 and k=6, plus algorithmic consequences.
-
Vertex-critical co-gem-free graphs
There are finitely many k-vertex-critical (co-gem, house)-free graphs and (co-gem, dart)-free graphs for every k ≥ 1.