A survey of χ‐boundedness

2020/08/24 by Alex Scott, Paul Seymour · 12 citations

paper · doi:10.1002/jgt.22601

Abstract

Abstract If a graph has bounded clique number and sufficiently large chromatic number, what can we say about its induced subgraphs? András Gyárfás made a number of challenging conjectures about this in the early 1980s, which have remained open until recently; but in the last few years there has been substantial progress. This is a survey of where we are now.

Cited by

• Optimal coloring of \cap,even hole\-free graphs with no short odd holes
• Coloring Geometric Hypergraphs: A Survey
• On the analogue of Esperet's conjecture: Characterizing hereditary classes
• Awesome graph parameters
• Burling graphs in graphs with large chromatic number
• A CSP approach to Graph Sandwich Problems
• Fractionally colouring P₅-free graphs
• Counterexamples to Wegner's Conjecture for Rectangles
• Optimal binding function for (cap,even hole)-free graphs with no short odd holes
• Graphs with girth 2ℓ and without longer even holes are 3-colorable
• Fractional domatic number and minimum degree
• Binary matroids and degree-boundedness for pivot-minors

Related

• A survey of χ-boundedness
• Induced subgraphs of graphs with large chromatic number. VII. Gyárfás' complementation conjecture
• Burling graphs in graphs with large chromatic number
• A survey of degree-boundedness
• Chromatic number, Clique number, and Lovász's bound: In a comparison