Colouring graphs with no induced six-vertex path or diamond

DOI10.1007/978-3-030-89543-3_27OpenAlexW3208599115MaRDI QIDQ5972261

Jan Goedgebeur, Yiao Ju, Owen Merkel, Shenwei Huang

Publication date: 30 March 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-89543-3_27

zbMATH Keywords

graph colouringdiamond-free graph\(P_6\)-free graph\(k\)-critical graph

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Related Items (3)

THE CHROMATIC NUMBER OF -FREE GRAPHS ⋮ Improved bounds on the chromatic number of (\(P_5\), flag)-free graphs ⋮ On some generalized vertex Folkman numbers

Uses Software

• House of Graphs
• CriticalPfreeGraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Certifying algorithms
• The strong perfect graph theorem
• The ellipsoid method and its consequences in combinatorial optimization
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Linearly \(\chi\)-bounding \((P_6,C_4)\)-free graphs
• House of Graphs: a database of interesting graphs
• Obstructions for three-coloring graphs without induced paths on six vertices
• Vertex-critical \((P_5\), banner)-free graphs
• Colouring diamond-free graphs
• On the chromatic number of (\(P_6\), diamond)-free graphs
• Vizing bound for the chromatic number on some graph classes
• Exhaustive generation of k‐critical ‐free graphs
• Coloring (gem, co‐gem)‐free graphs
• Square-Free Graphs with No Six-Vertex Induced Path
• A BOUND FOR THE CHROMATIC NUMBER OF (, GEM)-FREE GRAPHS
• Four-coloring P₆-free graphs
• An optimal χ‐bound for (P6, diamond)‐free graphs
• Coloring graphs with no induced five‐vertex path or gem

This page was built for publication: Colouring graphs with no induced six-vertex path or diamond