On graphs without four-vertex induced subgraphs

DOI10.1016/J.DAM.2026.02.030MaRDI QIDQ7238584zbMATH OpenFDO

Authors Kathie Cameron, Chính T. Hoàng, Taite LaGrange

Publication date 8 May 2026

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2026.02.030

zbMATH Keywords

\(C_4\)-twinbridgeclawclique-widthgraph colouringline-graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Cites work

• A coloring algorithm for \(4 K_1\)-free line graphs
• Characterizations of derived graphs
• Clique-width for 4-vertex forbidden subgraphs
• How To Color Claw-Free Perfect Graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• On coloring a class of claw-free graphs.
• On the structure of graphs without claw, \(4K_1\) and co-R
• Recognizing claw-free perfect graphs
• The strong perfect graph theorem
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• Topics on perfect graphs
• Upper bounds to the clique width of graphs
• Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs
• Vertex coloring of graphs with few obstructions

This page was built for publication: On graphs without four-vertex induced subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7238584)