Induced subgraphs of graphs with large chromatic number. I. Odd holes
From MaRDI portal
(Redirected from Publication:326809)
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.
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
- scientific article; zbMATH DE number 1002021 (Why is no real title available?)
- scientific article; zbMATH DE number 3747156 (Why is no real title available?)
- scientific article; zbMATH DE number 3480625 (Why is no real title available?)
- scientific article; zbMATH DE number 4183452 (Why is no real title available?)
- Graph Classes: A Survey
- Graph Theory and Probability
- Induced cycles and chromatic number
- Induced subtrees in graphs of large chromatic number
- Radius Three Trees in Graphs with Large Chromatic Number
- Radius two trees specify χ‐bounded classes
- Recognizing Berge graphs
- The strong perfect graph theorem
- \(K_{4}\)-free graphs with no odd holes
Cited in
(49)- Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths
- 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
- On graphs with no induced five‐vertex path or paraglider
- A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number
- Some problems on induced subgraphs
- Detecting a long odd hole
- Triangle packings and transversals of some \(K_{4}\)-free graphs
- Problems close to my heart
- The chromatic number of {ISK4, diamond, bowtie}‐free graphs
- \(K_{4}\)-free graphs with no odd hole: even pairs and the circular chromatic number
- Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
- Some remarks on graphs with no induced subdivision of \(K_4\)
- Graphs with no even holes and no sector wheels are the union of two chordal graphs
- \(K_{4}\)-free graphs with no odd holes
- Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case
- Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors
- Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
- Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures
- Square-Free Graphs with No Six-Vertex Induced Path
- 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
- 2-divisibility of some odd hole free graphs
- THE CHROMATIC NUMBER OF -FREE GRAPHS
- A better upper bound on the chromatic number of (cap, even-hole)-free graphs
- Coloring of \((P_5, 4\)-wheel)-free graphs
- A note on a conjecture of Wu, Xu and Xu
- On the chromatic number of a family of odd hole free graphs
- Restricted frame graphs and a conjecture of Scott
- A Generalization of $$\chi $$-Binding Functions
- Induced subgraphs of graphs with large chromatic number. III: Long holes
- Induced subgraphs of graphs with large chromatic number. IV: Consecutive holes
- A note on chromatic number and induced odd cycles
- Graphs of large chromatic number
- A note on chromatic number of (cap, even hole)-free graphs
- An optimal χ‐bound for (P6, diamond)‐free graphs
- A tight linear bound to the chromatic number of \((P_5, K_1 +(K_1 \cup K_3))\)-free graphs
- Induced odd cycle packing number, independent sets, and chromatic number
- Polynomial bounds for chromatic number VII. Disjoint holes
- Graphs with girth 9 and without longer odd holes are 3-colourable
- Colouring exact distance graphs of chordal graphs
- Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
- Borodin-Kostochka conjecture holds for odd-hole-free graphs
- Maximum odd induced subgraph of a graph concerning its chromatic number
- Characterization of forbidden subgraphs for bounded star chromatic number
- Pure pairs. II: Excluding all subdivisions of a graph
- Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
- Divisibility and coloring of some \(P_5\)-free graphs
- Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions
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)
