Triangle-free graphs with no six-vertex induced path

DOI10.1016/j.disc.2018.04.020zbMath1388.05098OpenAlexW2804507962WikidataQ129797070 ScholiaQ129797070MaRDI QIDQ1637133

Sophie Spirkl, Maria Chudnovsky, Mingxian Zhong, P. D. Seymour

Publication date: 7 June 2018

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

Full work available at URL: https://doi.org/10.1016/j.disc.2018.04.020

zbMATH Keywords

induced subgraphinduced path

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40)

Related Items

Graph classes with linear Ramsey numbers, An optimal χ‐bound for (P6, diamond)‐free graphs, Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring, Unnamed Item, Graphs without five-vertex path and four-vertex cycle, Colouring (P_r+P_s)-Free Graphs, Colouring square-free graphs without long induced paths

Cites Work

• Unnamed Item
• Ramsey-type theorems
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Bipartite graphs without a skew star
• The Erdös-Hajnal Conjecture-A Survey
• Independent Set in P₅-Free Graphs in Polynomial Time