Induced subgraphs of graphs with large chromatic number. I. Odd holes

DOI10.1016/j.jctb.2015.10.002zbMath1412.05076arXiv1410.4118OpenAlexW2560122957MaRDI QIDQ326809

P. D. Seymour, Alexander D. Scott

Publication date: 12 October 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

colouringinduced subgraphsodd holes

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (37)

Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case ⋮ 2-divisibility of some odd hole free graphs ⋮ Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions ⋮ A note on chromatic number and induced odd cycles ⋮ Triangle packings and transversals of some \(K_{4}\)-free graphs ⋮ THE CHROMATIC NUMBER OF -FREE GRAPHS ⋮ The chromatic number of {ISK4, diamond, bowtie}‐free graphs ⋮ On graphs with no induced five‐vertex path or paraglider ⋮ Some remarks on graphs with no induced subdivision of \(K_4\) ⋮ Induced odd cycle packing number, independent sets, and chromatic number ⋮ An optimal χ‐bound for (P6, diamond)‐free graphs ⋮ Problems close to my heart ⋮ Some problems on induced subgraphs ⋮ Divisibility and coloring of some \(P_5\)-free graphs ⋮ Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors ⋮ Borodin-Kostochka conjecture holds for odd-hole-free graphs ⋮ A Generalization of $$\chi $$-Binding Functions ⋮ Graphs of large chromatic number ⋮ A tight linear bound to the chromatic number of \((P_5, K_1 +(K_1 \cup K_3))\)-free graphs ⋮ Characterization of forbidden subgraphs for bounded star chromatic number ⋮ A note on chromatic number of (cap, even hole)-free graphs ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ A better upper bound on the chromatic number of (cap, even-hole)-free graphs ⋮ Induced subgraphs of graphs with large chromatic number. VII: Gyárfás' complementation conjecture ⋮ Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors ⋮ Induced subgraphs of graphs with large chromatic number. III: Long holes ⋮ Induced subgraphs of graphs with large chromatic number. IV: Consecutive holes ⋮ Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes ⋮ Detecting a long odd hole ⋮ Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings ⋮ Pure pairs. II: Excluding all subdivisions of a graph ⋮ Colouring exact distance graphs of chordal graphs ⋮ Square-Free Graphs with No Six-Vertex Induced Path ⋮ A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number ⋮ A note on a conjecture of Wu, Xu and Xu ⋮ Coloring of \((P_5, 4\)-wheel)-free graphs ⋮ Restricted frame graphs and a conjecture of Scott

Cites Work

• The strong perfect graph theorem
• \(K_{4}\)-free graphs with no odd holes
• Induced subtrees in graphs of large chromatic number
• Induced cycles and chromatic number
• Recognizing Berge graphs
• Graph Theory and Probability
• Graph Classes: A Survey
• Radius two trees specify χ‐bounded classes
• Radius Three Trees in Graphs with Large Chromatic Number
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Induced subgraphs of graphs with large chromatic number. I. Odd holes