View PDF HTML (experimental)

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.

Submission history

From: Chinh Hoang [view email]
[v1] Thu, 30 Apr 2026 08:43:57 UTC (16 KB)
[v2] Sat, 16 May 2026 02:26:40 UTC (17 KB)
[v3] Sat, 18 Jul 2026 22:26:28 UTC (17 KB)