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

DOI10.1016/J.JCTB.2019.08.008zbMATH Open1436.05076arXiv1701.06301OpenAlexW2972211570MaRDI QIDQ1985444FDOQ1985444

Authors: Alex Scott, Paul Seymour 

Publication date: 7 April 2020

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

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$.

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

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

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)

Cites Work

• Normal hypergraphs and the perfect graph conjecture
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Title not available (Why is that?)
• Recognizing Berge graphs
• Complements of nearly perfect graphs
• Coloring non-crossing strings
• Coloring Jordan regions and curves

Cited In (20)

• From \(\chi\)- to \(\chi_p\)-bounded classes
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• 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
• Polynomial bounds for chromatic number VII. Disjoint holes
• Induced subgraphs of graphs with large chromatic number. III: Long holes
• χ‐bounded families of oriented graphs
• Some problems on induced subgraphs
• Induced subgraphs of graphs with large chromatic number. XIII. New brooms
• Problems close to my heart
• Complements of nearly perfect graphs
• Polynomial bounds for chromatic number VI. Adding a four-vertex path
• On the chromatic number of (P_{5},windmill)-free graphs
• A survey of \(\chi\)-boundedness
• 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. 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)