Structural description of (bull, house)-free graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.27594
curl -X POST /api/v1/records/arxiv/2604.27594/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.27594/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'