Near optimal colourability on hereditary graph families

DOI10.1016/j.tcs.2024.114465arXiv2303.18003MaRDI QIDQ6196836

Shenwei Huang, Yiao Ju

Publication date: 15 March 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

polynomial time algorithmgraph colouringforbidden induced subgraphsLovász theta function

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The strong perfect graph theorem
• Paw-free graphs
• A bound on the chromatic number of graphs without certain induced subgraphs
• The ellipsoid method and its consequences in combinatorial optimization
• On the chromatic number of \(2 K_2\)-free graphs
• On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Graphs with no induced \(C_ 4\) and \(2K_ 2\)
• Vertex colouring and forbidden subgraphs -- a survey
• Graph Theory and Probability
• A survey of χ‐boundedness
• Four-coloring P₆-free graphs
• Colouring graphs with no induced six-vertex path or diamond

This page was built for publication: Near optimal colourability on hereditary graph families