Colouring graphs with no induced six-vertex path or diamond
From MaRDI portal
Publication:5925590
DOI10.1016/j.tcs.2022.11.020OpenAlexW3171062666MaRDI QIDQ5925590
Jan Goedgebeur, Yiao Ju, Owen Merkel, Shenwei Huang
Publication date: 4 January 2023
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2106.08602
graph colouringpolynomial-time algorithms\(\chi\)-boundednessLovász theta functionstrong perfect graph theorem
Related Items (1)
Uses Software
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
- Optimal wavelength routing on directed fiber trees
- House of graphs 2.0: a database of interesting graphs and more
- 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 P6-free graphs
- The complexity of path coloring and call scheduling
- 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
