There are finitely many 5-vertex-critical (P₆,bull)-free graphs

2025/04/19 by Ju, Yiao, Jooken, Jorik, Goedgebeur, Jan +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2504.14134

Abstract

In this paper, we are interested in 4-colouring algorithms for graphs that do not contain an induced path on 6 vertices nor an induced bull, i.e., the graph with vertex set \v₁,v₂,v₃,v₄,v₅\ and edge set \v₁v₂,v₂v₃,v₃v₄,v₂v₅,v₃v₅\. Such graphs are referred to as (P₆,bull)-free graphs. A graph G is k-vertex-critical if χ(G)=k, and every proper induced subgraph H of G has χ(H)

Related

• A refinement on the structure of vertex-critical (P₅, gem)-free graphs
• Some Results on k-Critical P₅-Free Graphs
• Some Results on Critical (P₅,H)-free Graphs
• Vertex-Critical (P₅, chair)-Free Graphs
• k-Critical Graphs in P₅-Free Graphs