Induced subgraphs of graphs with large chromatic number. VII: Gyárfás' complementation conjecture

DOI10.1016/J.JCTB.2019.08.008MaRDI QIDQ1985444zbMATH OpenOpenAlexFDO

Authors Alex Scott, Paul Seymour

Publication date 7 April 2020

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

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

zbMATH Keywords

\(\chi\)-boundedchromatic numberinduced subgraphscliques

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Abstract: A class of graphs is $chi$-bounded if there is a function $f$ such that $chi(G)lef(omega(G))$ for every induced subgraph $G$ of every graph in the class, where $chi,omega$ denote the chromatic number and clique number of $G$ respectively. In 1987, Gy'arf'as conjectured that for every $c$, if $mathcalC$ is a class of graphs such that $chi(G)leomega(G)+c$ for every induced subgraph $G$ of every graph in the class, then the class of complements of members of $mathcalC$ is $chi$-bounded. We prove this conjecture. Indeed, more generally, a class of graphs is $chi$-bounded if it has the property that no graph in the class has $c+1$ odd holes, pairwise disjoint and with no edges between them. The main tool is a lemma that if $C$ is a shortest odd hole in a graph, and $X$ is the set of vertices with at least five neighbours in $V(C)$, then there is a three-vertex set that dominates $X$.

Recommendations

• Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
• Some problems on induced subgraphs
• A survey of \(\chi\)-boundedness

Cites work

• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• Coloring Jordan regions and curves
• Coloring non-crossing strings
• Complements of nearly perfect graphs
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Normal hypergraphs and the perfect graph conjecture
• Recognizing Berge graphs

Cited in

(20)

• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• From \(\chi\)- to \(\chi_p\)-bounded classes
• Excluding induced subdivisions of the bull and related graphs
• Extending the Gyárfás-Sumner conjecture
• Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures
• Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths
• Induced subgraphs of graphs with large chromatic number. III: Long holes
• Polynomial bounds for chromatic number VII. Disjoint holes
• χ‐bounded families of oriented graphs
• Some problems on induced subgraphs
• Induced subgraphs of graphs with large chromatic number. XIII. New brooms
• Complements of nearly perfect graphs
• Polynomial bounds for chromatic number VI. Adding a four-vertex path
• Problems close to my heart
• On the chromatic number of (P_{5},windmill)-free graphs
• A better upper bound on the chromatic number of (cap, even-hole)-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 survey of \(\chi\)-boundedness
• 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. VII: Gyárfás' complementation conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1985444)