Induced subgraphs of graphs with large chromatic number. I. Odd holes
From MaRDI portal
Publication:326809
DOI10.1016/J.JCTB.2015.10.002zbMATH Open1412.05076arXiv1410.4118OpenAlexW2560122957MaRDI QIDQ326809FDOQ326809
Publication date: 12 October 2016
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Abstract: An odd hole in a graph is an induced subgraph which is a cycle of odd length at least five. In 1985, A. Gyarfas made the conjecture that for all t there exists n such that every graph with no K_t subgraph and no odd hole is n-colourable. We prove this conjecture.
Full work available at URL: https://arxiv.org/abs/1410.4118
Recommendations
- Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
- 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. X. Holes of specific residue
- Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures
- Induced subgraphs of graphs with large chromatic number. VII: Gyárfás' complementation conjecture
- Induced subgraphs of graphs with large chromatic number. XIII. New brooms
- Induced subgraphs of graphs with large chromatic number. XI. Orientations
- Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
- Odd induced subgraphs in planar graphs with large girth
Cites Work
- Induced cycles and chromatic number
- Title not available (Why is that?)
- Graph Theory and Probability
- Title not available (Why is that?)
- Graph Classes: A Survey
- Title not available (Why is that?)
- The strong perfect graph theorem
- Recognizing Berge graphs
- Title not available (Why is that?)
- Induced subtrees in graphs of large chromatic number
- Radius two trees specify χ‐bounded classes
- Radius Three Trees in Graphs with Large Chromatic Number
- \(K_{4}\)-free graphs with no odd holes
Cited In (44)
- Restricted frame graphs and a conjecture of Scott
- Pure pairs. II: Excluding all subdivisions of a graph
- Graphs with girth 9 and without longer odd holes are 3-colourable
- Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors
- Coloring of \((P_5, 4\)-wheel)-free graphs
- Some remarks on graphs with no induced subdivision of \(K_4\)
- Borodin-Kostochka conjecture holds for odd-hole-free graphs
- Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
- Characterization of forbidden subgraphs for bounded star chromatic number
- Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths
- The chromatic number of {ISK4, diamond, bowtie}‐free graphs
- Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case
- Detecting a long odd hole
- Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
- Induced odd cycle packing number, independent sets, and chromatic number
- 2-divisibility of some odd hole free graphs
- THE CHROMATIC NUMBER OF -FREE GRAPHS
- An optimal χ‐bound for (P6, diamond)‐free graphs
- A Generalization of $$\chi $$-Binding Functions
- Graphs of large chromatic number
- Polynomial bounds for chromatic number VII. Disjoint holes
- Induced subgraphs of graphs with large chromatic number. III: Long holes
- Induced subgraphs of graphs with large chromatic number. IV: Consecutive holes
- 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
- Colouring exact distance graphs of chordal graphs
- Induced subgraphs of graphs with large chromatic number. VII: Gyárfás' complementation conjecture
- Square-Free Graphs with No Six-Vertex Induced Path
- On the chromatic number of a family of odd hole free graphs
- Some problems on induced subgraphs
- On graphs with no induced five‐vertex path or paraglider
- Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
- Induced subgraphs of graphs with large chromatic number. XIII. New brooms
- Problems close to my heart
- Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
- A note on a conjecture of Wu, Xu and Xu
- A tight linear bound to the chromatic number of \((P_5, K_1 +(K_1 \cup K_3))\)-free graphs
- A note on chromatic number of (cap, even hole)-free graphs
- Divisibility and coloring of some \(P_5\)-free graphs
- Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
- Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue
- A better upper bound on the chromatic number of (cap, even-hole)-free graphs
- A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number
This page was built for publication: Induced subgraphs of graphs with large chromatic number. I. Odd holes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q326809)
