On k-colorability of (bull, H)-free graphs

2025/09/01 by Nadzieja Hodur, Monika Pilśniak, Hodur, Nadzieja +5 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2509.01698

openalex publication_date 2025/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The 3-colorability problem is a well-known NP-complete problem and it remains NP-complete for bull-free graphs, where a bull is the graph consisting of a K₃ with two pendant edges attached to two of its vertices. In this paper, for k≥3, we characterize all k-colorable (bull,claw)-free graphs containing an induced cycle of length at least 6. Moreover, we present the full characterization of all non 4-colorable connected (bull,claw)-free graphs and (bull,chair, C₅)-free graphs, and all non 5-colorable connected (bull, claw, C₅)-free graphs.

Citations

• Finding large k-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs
• Perfect divisibility and coloring of some fork-free graphs
• Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4
• On forbidden induced subgraphs for K_1,3-free perfect graphs
• Detecting an odd hole
• Obstructions for three-coloring graphs without induced paths on six vertices
• A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs
• The strong perfect graph theorem

Cited by

• Perfect Divisibility and Coloring of Some Bull-Free Graphs
• Structure, Perfect Divisibility and Coloring of (P₂∪ P₄, C₃)-Free Graphs

Related

• On 3-colourability of (bull, H)-free graphs
• Colouring Generalized Claw-Free Graphs and Graphs of Large Girth: Bounding the Diameter
• Obstructions for three-coloring and list three-coloring H-free graphs
• 4-coloring (P₆, bull)-free graphs
• A certifying algorithm for 3-colorability of P5-free graphs