{"id":"arxiv/2604.27594","url":"https://arxiv.org/abs/2604.27594","tags":["math.CO"],"score":0,"title":"Structural description of (bull, house)-free graphs","domain":"math.CO","source":"arxiv","authors":["Manoj Belavadi","Chinh T. Hoang"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-30","reactions":{}}