Linearly χ‐bounding (P6, C4)‐free graphs*

DOI10.1002/jgt.22456zbMath1429.05067arXiv1709.09750OpenAlexW2920083926MaRDI QIDQ5207472

Shenwei Huang, Serge Gaspers

Publication date: 30 December 2019

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1709.09750

zbMATH Keywords

approximation algorithmgraph coloringforbidden induced subgraphsstructure theoremlinear \(\chi \)-bound

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Related Items (4)

THE CHROMATIC NUMBER OF -FREE GRAPHS ⋮ An optimal χ‐bound for (P6, diamond)‐free graphs ⋮ Strengthening Brooks' chromatic bound on \(P_6\)-free graphs ⋮ A better upper bound on the chromatic number of (cap, even-hole)-free graphs

This page was built for publication: Linearly χ‐bounding (P₆, C₄)‐free graphs*