On graphs without four-vertex induced subgraphs

2025/04/30 by Cameron, Kathie, Hoàng, Chính T., LaGrange, Taite
#05C15 #Combinatorics (math.CO) #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.2505.00202

Abstract

Given a family F of graphs, a graph G is F-free if it does not contain any graph in F as an induced subgraph. The problem of determining the complexity of colouring (claw, 4K1)- free graphs is a well-known open problem. In this paper we solve the colouring problem for a subclass of (claw, 4K1)-free graphs. We design a polynomial-time algorithm to colour (claw, 4K1, bridge, C4-twin)-free graphs. This algorithm is derived from a structural theorem on (claw, 4K1, bridge, C4-twin)-free graphs.

Citations

• A Coloring Algorithm for 4K₁-free line graphs
• The strong perfect graph theorem

Related

• On the structure of (4K₁, C₄, P₆)-free graphs
• Classifying k-Edge Colouring for H-free Graphs
• Colouring Generalized Claw-Free Graphs and Graphs of Large Girth: Bounding the Diameter
• A Coloring Algorithm for 4K₁-free line graphs
• On Colouring (2P₂,H)-Free and (P₅,H)-Free Graphs