On 3-colourability of (bull, H)-free graphs

2024/04/18 by Nadzieja Hodur, Monika Pilśniak, Hodur, Nadzieja +5
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2404.12515

openalex publication_date 2024/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The 3-colourability problem is a well-known NP-complete problem and it remains NP-complete for bull-free graphs, where bull is the graph consisting of K₃ with two pendant edges attached to two of its vertices. In this paper we study 3-colourability of (bull,H)-free graphs for several graphs H. We show that these graphs are 3-colourable or contain an induced odd wheel W_2p+1 for some p≥ 2 or a spindle graph M_3p+1 for some p≥ 1. Moreover, for all our results we can provide certifying algorithms that run in polynomial time.

Related

• On k-colorability of (bull, H)-free graphs
• 3-Colouring P_t-free graphs without short odd cycles
• Graphs with large minimum degree and no small odd cycles are 3-colourable
• 3-Coloring C₄ or C₃-free Diameter Two Graphs
• Colouring Generalized Claw-Free Graphs and Graphs of Large Girth: Bounding the Diameter