PaperlayerView exact revision on arXiv

Source-linked AI summary

A survey of $χ$-boundedness

Alex Scott, Paul Seymour

arXiv:1812.07500v3math.CO

TL;DR

This survey examines what induced subgraphs must occur in graphs with bounded clique number and sufficiently large chromatic number, focusing on questions originating with Gyárfás. It synthesizes substantial recent progress, including odd-hole results, χ-boundedness conjectures, and counterexamples concerning subdivisions.

  • Problem

    The survey asks what induced subgraphs can be forced when clique number is bounded but chromatic number is sufficiently large.

  • Method

    The paper surveys conjectures, theorems, proof methods, variants, and counterexamples concerning χ-boundedness and induced subgraphs.

  • Results

    The survey records that χ(G) > ω(G) forces an odd hole or odd antihole, while χ(G) > 22κ+2 with ω(G) ≤κ forces an odd hole, and all forests are χ-bounding.

  • Takeaways & Limitations

    Recent progress strengthens structural conclusions for high-chromatic graphs and establishes χ-boundedness results for several graph classes, including forests and graphs excluding holes of prescribed lengths modulo ℓ.

  • Takeaways & Limitations

    The conjecture that every graph is weakly pervasive is false: the Burling graph contains no induced subdivision of a 1-subdivision of K5.

Abstract

from arXiv · show

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 1980's, 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.

1 Introduction

The introduction asks whether graphs with bounded clique number and sufficiently large chromatic number must contain stronger induced structures, framing the question through χ-bounded ideals. It highlights an odd-hole theorem as a major strengthening of the strong perfect graph theorem.

  • 1 Introduction: If χ(G) > ω(G), then G contains an induced odd hole or odd antihole.This is the strong perfect graph theorem’s structural conclusion.
  • 1 Introduction: The strong perfect graph theorem settled a long-standing open question about perfect graphs.
  • 1 Introduction: For every κ ≥0, ω(G) ≤κ and χ(G) > 22κ+2 imply that G has an odd hole.
  • 1 Introduction: An ideal is a graph class closed under isomorphism and induced subgraphs, and it is χ-bounded when χ(G) is bounded by a function of ω(G).
  • 1 Introduction: The survey organizes results into forests, holes, and other topics, alongside related questions and open problems.

2 Examples

This section presents triangle-free graphs with arbitrarily large chromatic number, using explicit, probabilistic, and recursive constructions. The examples illustrate how large chromatic number can coexist with restricted clique, cycle, or neighborhood structure.

  • 2 Examples: Triangle-free graphs with arbitrarily large chromatic number exist, and many constructions are explicit.The section uses these graphs as examples of bounded clique number with large chromatic number.
  • 2 Examples: Tutte’s recursive construction produces triangle-free graphs, indeed of girth at least six, whose chromatic number grows beyond each inductive threshold.
  • 2 Examples: Mycielski’s graphs are triangle-free with chromatic number k, but every triangle-free graph is an induced subgraph of some such graph.Consequently, this construction does not provide a useful source of graphs with forbidden induced subgraphs.
  • 2 Examples: For k = 3, the tuple construction has a proper middle-element colouring in which every vertex sees only two neighbour colours.
  • 2 Examples: Kim’s construction yields triangle-free graphs with O(t2 log t) vertices and chromatic number Ω(t log t).Explicit constructions also achieve Ω(t3/2) vertices with no stable set of size t and chromatic number Ω(t1/2).
  • 2 Examples: Burling’s recursive graphs have no triangles and satisfy χ(Gk) ≥k + 1.The construction maintains a stable set Tk whose vertices witness increasingly many neighbour colours.

3 The Gy´arf´as-Sumner conjecture

The Gyárfás-Sumner conjecture asserts that every forest is χ-bounding, but only substantial families of trees are known. Recent results extend χ-boundedness to several trees with separated high-degree vertices, while induced subdivisions provide a weaker theorem for every tree.

  • 3.1 The Gyárfás-Sumner conjecture: The Gyárfás-Sumner conjecture states that all forests are χ-bounding.Only forests can be χ-bounding as forbidden induced graphs, since graphs of sufficiently large girth can be triangle-free with arbitrarily large chromatic number.
  • Weaker results: For every tree T, graphs with no induced subdivision of T form a χ-bounded ideal, although the original forest conjecture remains open.
  • Known cases: Every path is χ-bounding, proved by bounding neighbourhoods and inducting on path length and clique number.The proof uses a lemma controlling connected graphs without a long induced path from a specified vertex.
  • Recent progress: Trees formed from a radius-two tree by subdividing some root-incident edges are χ-bounding.This unifies earlier results for radius-two trees and trees obtained by subdividing every root-incident edge.
  • Recent progress: Several trees with far-apart vertices of degree more than two are χ-bounding, including trees joining a star and star subdivision by a path.Other cases include adding one vertex to a star subdivision and joining two disjoint paths by an edge.
  • Proof methods: These recent proofs combine induction on clique number with distance layers from a chosen vertex and structural classification of vertices.The earlier template method instead analyzes attachments to large complete multipartite structures.

4 Variants of Gy´arf´as-Sumner: rainbow subgraphs

For graphs with bounded clique number and sufficiently large chromatic number, every proper colouring contains a long rainbow induced path. This resolves the broader rainbow-subgraph question because paths and disjoint unions of paths are exactly the possible targets, while a stronger triangle-free conjecture remains open.

  • Rainbow induced paths: Only paths and disjoint unions of paths can be guaranteed as rainbow induced subgraphs in all such colourings.Graphs containing cycles may be absent, while graphs with a vertex of degree more than two can be avoided by suitable colourings.
  • Rainbow induced paths: Graphs with bounded clique number and sufficiently large chromatic number contain an s-vertex rainbow induced path under every proper colouring.The threshold c depends on κ and s.
  • Proof idea: The proof explores vertices reachable by rainbow paths, repeatedly extending induced paths while reachable sets retain large chromatic number.A second case handles when every reachable set has small chromatic number, using related colouring theorems.
  • Open direction: Aravind conjectured that every colouring of a triangle-free graph contains a χ(G)-vertex rainbow induced path.The conjecture remains open, although induced-only and rainbow-only variants are known, as is a special case tied to girth.

5 Variants of Gy´arf´as-Sumner: orientations

The survey examines which induced oriented subgraphs must occur in high-chromatic graphs with bounded clique number. It proves χ-boundedness for graphs admitting orientations that avoid specified directed four-vertex paths or directed stars, while the general oriented-tree question remains open.

  • Directed paths: Several orientations of the four-vertex path cannot be guaranteed as induced subdigraphs, including →←→ and →→→.The counterexamples use orientations of shift graphs.
  • Directed paths: The ideal of graphs that can be oriented with no induced →←← is χ-bounded.This answers a question raised for the general, not only acyclic, orientation setting.
  • Directed stars: For every orientation H of a star, graphs admitting an orientation with no induced H form a χ-bounded ideal.This settles the mixed in-and-out directed-star case.
  • Open direction: The characterization of oriented trees with this property is unresolved beyond excluding four-vertex paths directed as →←→ or →→→.The survey identifies this as an open question and points to further discussion elsewhere.

6 Holes

The survey presents χ-boundedness results for graph classes excluding holes of specified lengths or patterns, including strong theorems on modular hole lengths and related conjectures.

  • Bounded hole lengths: Every graph with no hole of length greater than ℓ is χ-bounded.A stronger theorem also handles graphs with no hole of a specified residue class modulo ℓ.
  • Bounded hole lengths: The three principal Gyárfás conjectures on holes have all been proved, with the strongest result covering them and theorem 6.4.Their proofs use levellings and bounds on chromatic numbers of bounded-radius balls.
  • Other hole restrictions: Every graph with no even hole has chromatic number at most twice its clique number.The result would follow from a proof that such graphs have bisimplicial vertices, after an earlier proof was withdrawn because of an error.
  • Other hole restrictions: Every graph with sufficiently large chromatic number contains either a triangle or a hole whose length is divisible by three.This implies bounded chromatic number for the ideal where every induced subgraph has nearly equal odd- and even-stable-set counts.
  • Modular hole lengths: Every graph with no hole of length k modulo ℓ is χ-bounded for all integers k ≥0 and ℓ≥1.This theorem subsumes the three Gyárfás conjectures and theorem 6.4.
  • Consecutive hole lengths: For every ℓ, some k ensures that every triangle-free graph with χ(G)>k contains ℓ holes of consecutive lengths.The general conjecture remains open, and the proof currently has no extension to graphs containing triangles.

7 Subdivisions

The survey studies induced subdivisions through weakly pervasive, pervasive, and widespread graphs, proving broad results for forests of chandeliers and controlled graph ideals while leaving a central characterization open.

  • Weak pervasiveness: For every cycle C and tree T, graphs containing no induced subdivision of C or T form χ-bounded ideals.These results motivate the broader notions of weak pervasiveness and pervasiveness.
  • Weak pervasiveness: A 1-subdivision of K5 is not weakly pervasive because the Burling graph contains no induced subdivision of it.This disproves the conjecture that every graph is weakly pervasive.
  • Pervasiveness: Every banana tree is pervasive, and a graph is conjectured to be pervasive in all graphs exactly when it is a forest of chandeliers.A forest of chandeliers is built recursively by identifying chandelier pivots with existing vertices.
  • Controlled ideals: Every forest of chandeliers is pervasive in every r-controlled ideal for r≥2.Here r-controlled means chromatic number is bounded as a function of the maximum chromatic number of r-balls in every induced subgraph.
  • Controlled ideals: In a 2-controlled ideal with bounded clique number, sufficiently large chromatic number yields either a forest of chandeliers H or an induced 1-subdivision of K_m,m.A preceding theorem reduces suitable r-controlled subdivision-free ideals to 2-controlled ideals.
  • Widespread graphs: A widespread multigraph that is not a forest of chandeliers shows that the expected characterization of widespread graphs is false and remains unresolved.The example is obtained from a triangle by adding parallel edges, and the status of whether all graphs are widespread is tied to the 2-controlled case.

8 Graphs with geometric representations

Geometric graph classes provide both χ-bounded and non-χ-bounded examples, while string graphs are especially useful because they are 2-controlled and support induced-subdivision results.

  • Intersection graphs: Interval graphs and 2-dimensional box graphs are χ-bounded, whereas 3-dimensional box graphs are not.The failure for 3-dimensional boxes follows from realizing the Burling construction in that class.
  • Intersection graphs: The Burling construction yields triangle-free intersection graphs of line segments in the plane with arbitrarily large chromatic number.This resolves an Erdős question about whether that geometric ideal contains such graphs.
  • Intersection graphs: The ideal of intersection graphs of unit segments in the plane is χ-bounded.This is a χ-bounded subideal of the broader string-graph class.
  • Intersection graphs: For every t≥1, intersection graphs of curves each crossing a fixed curve between one and t times are χ-bounded.This provides a broad geometric χ-boundedness theorem.
  • String graphs: The ideal of string graphs is 2-controlled.Large chromatic number in this class therefore produces a small ball with large chromatic number, a property used in subdivision arguments.
  • Visibility graphs: Visibility graphs with clique number at most four have bounded chromatic number, but visibility graphs with clique number six can have arbitrarily large chromatic number.The latter result disproves the conjecture that bounded clique number always suffices for visibility graphs.

9 Connections: the Erd˝os-Hajnal conjecture

The section develops strong Erdős–Hajnal results for ideals excluding forests and their complements, and highlights connections with χ-boundedness and induced subdivisions.

  • Erdős–Hajnal property: Every H-free ideal has the Erdős–Hajnal property if its graphs contain cliques or stable sets of size |G|^ε.The conjecture asserts this for every graph H.
  • Connections: χ-boundedness with a polynomial binding function implies the Erdős–Hajnal property, but the converse fails for triangle-free graphs.For a χ-binding function f, α(G)f(ω(G)) ≥ |G|; triangle-free graphs nevertheless are not χ-bounded.
  • Strong Erdős–Hajnal property: For every forest H, every H-free graph either has a vertex of degree at least ε|G| or two linear-sized anticomplete sets.This structural statement implies the strong Erdős–Hajnal property for graphs excluding both H and its complement.
  • Induced subdivisions: Excluding induced subdivisions of a cycle in both a graph and its complement gives the strong Erdős–Hajnal property.The result extends earlier work for paths and cycles to arbitrary pairs of graphs.
  • Induced subdivisions: For every graph H, every graph contains either an induced subdivision of H or two disjoint anticomplete sets of size at least ε|G|.This theorem yields strong Erdős–Hajnal results when induced subdivisions of two graphs are excluded.

10 Gy´arf´as’ complementation conjecture

The complementation question asks when χ-boundedness survives taking graph complements. The paper proves that every linear-plus-constant χ-binding bound transfers to complements.

  • Background: χ-boundedness is not generally preserved under complementation, although perfect graphs are closed under complements.Graphs with stability number at most two provide a χ-bounded class whose complements are not χ-bounded.
  • Main theorem: If χ(G) ≤ ω(G) + c for every G in an ideal I, then the ideal of complements of members of I is χ-bounded.This proves Gyárfás’ conjecture for every c ≥ 0.
  • Proof idea: The proof forbids c + 1 pairwise anticomplete odd holes in every graph in the complemented ideal.Otherwise, complementing produces c + 1 pairwise complete odd antiholes, violating the assumed chromatic bound.
  • Proof idea: The auxiliary statement bounds the chromatic number of graphs with clique number at most κ and no c + 1 pairwise anticomplete odd holes.The argument uses induction on c + κ and separates vertices according to their adjacency to a shortest odd hole.

11 Operations on χ-bounded ideals

The section studies which graph operations preserve χ-boundedness when applied to ideals. Substitution and several gluing operations preserve it individually, but combined closure remains open in general.

  • Preserving operations: Closure under gluing along cliques preserves χ-boundedness with the same χ-binding function.The closure is the smallest ideal containing the original class and closed under the operation.
  • Substitution: Closure under substitution preserves χ-boundedness, including polynomial and exponential χ-binding functions.Substitution replaces a vertex by a graph whose vertices inherit adjacency to the original vertex’s neighbours.
  • Gluing operations: Gluing along at most k vertices and 1-joins are also known to preserve χ-boundedness.Some combined closures, including substitution with clique gluing, are known to preserve χ-boundedness.
  • Open closure questions: It remains open whether closure under substitution and gluing along a bounded number of vertices is always χ-bounded.More generally, separate preservation by two operations does not currently imply preservation under their combined closure.
  • Open closure questions: Requiring closure under induced subgraphs is essential: without it, the corresponding combined-operation problem has a negative answer.The negative example uses the weaker notion of closure that omits induced-subgraph closure.

12 Open problems

The final section presents open problems on triangle-free induced subgraphs, polynomial χ-bounds, rainbow induced forests, and which hole-length sets force χ-boundedness.

  • Triangle-free induced subgraphs: Esperet’s conjecture asks whether sufficiently large chromatic number with bounded clique number forces a triangle-free induced subgraph of any prescribed chromatic number.Without the induced requirement, Rödl proved the analogous statement.
  • Triangle-free induced subgraphs: If true, the conjecture would reduce χ-boundedness questions to bounding chromatic number on triangle-free graphs in the ideal.The ideal condition is necessary for this equivalence.
  • Polynomial χ-boundedness: It is open whether every χ-bounded ideal is polynomially χ-bounded, which would imply the Erdős–Hajnal conjecture for every χ-bounded ideal.No ideal is currently known to be χ-bounded but not polynomially χ-bounded.
  • Polynomial χ-boundedness: For t ≥ 4, graphs with no induced t-vertex path satisfy χ(G) ≤ (t − 2)ω(G)^(t − 1).The case t = 5 being polynomially χ-bounded remains open, while known lower bounds require polynomial degree at least (t + 1)/4.
  • Growth of binding functions: It is unknown whether an optimal χ-binding value at clique number 2 controls the value at clique number 3.The case f_G(2) = 2 gives a bounded f_G(3), but the case f_G(2) = 3 remains unresolved.
  • Rainbow induced subgraphs: All forests, including stars and paths, are candidates for rainbow induced subgraphs in optimally coloured high-chromatic graphs, but the general forest case is open.Earlier results show that graphs with cycles or vertices of degree greater than two cannot satisfy the analogous arbitrary-colouring property.
  • Hole lengths: The paper conjectures that a set of hole lengths is constricting exactly when it has strictly positive lower density.This remains far from proved, and even a constricting set of upper density zero is not known to exist or not exist.
  • Hole lengths: Upper density cannot replace lower density: a non-χ-bounded ideal can omit a set of hole lengths with upper density 1.The construction uses triangle-free graphs with increasing girth and chromatic number.

12.7 Problem:

The survey poses conjectures about long consecutive hole lengths and induced odd subdivisions in graphs with large chromatic number, including variants that exclude complete bipartite subgraphs. It records a proved weakening for T-free graphs and a related theorem linking average degree to bicliques or induced clique subdivisions.

  • 12.7 Problem: A conjecture asks whether every triangle-free graph of sufficiently large chromatic number contains holes of f(t) consecutive lengths, each at most t, for some f(t) tending to infinity.The proposed function f satisfies f(t) →∞ as t →∞.
  • 12.7 Problem: Another conjecture asserts that graphs of sufficiently large chromatic number and sufficiently large girth contain holes of t consecutive lengths, for every t.The statement requires one fixed chromatic threshold k and sufficiently large girth.
  • 12.7 Problem: The Hajnal–Rödl weakening proves bounded chromatic number for T-free graphs that contain no K_n,n subgraph, even when the excluded biclique is not required to be induced.This holds for every tree T and integer n ≥ 0.
  • 12.7 Problem: Kühn and Osthus proved that every graph with sufficiently large average degree contains either a K_n,n subgraph or an induced subdivision of K_n.The result is stated for every integer n ≥ 0.
  • 12.7 Problem: The survey proposes replacing large average degree by large chromatic number and seeking an induced odd subdivision of K_n unless a K_n,n subgraph exists.An odd subdivision replaces every edge by a path of odd length.
  • 12.7 Problem: The proposed odd-subdivision problem is reduced through r-controlled ideals, with all but one resulting subproblem handled.The authors present this as a possible route to proving the conjecture.

Colouring graphs with no long holes

This section surveys bounds and conjectures for graphs with restricted holes, cycles with chords, and vertex-minor closure. It also highlights recent χ-boundedness results and the remaining algorithmic question of producing colourings efficiently.

  • Colouring graphs with no long holes: Short-holed graphs, in which every hole has length four, form a χ-bounded ideal, but the best possible dependence of chromatic number on clique number remains open.The survey asks how well χ can be bounded in terms of ω for this class.
  • Colouring graphs with no long holes: The known bounds may be far from optimal: the survey asks for a singly-exponential bound and notes the possibility that χ(G) ≤ω(G)^2 for short-holed graphs or graphs with no odd hole.These are presented as open possibilities rather than established bounds.
  • Colouring graphs with no long holes: The Hoàng–McDiarmid conjecture would partition every nonempty graph with no odd hole into two sets meeting every maximum clique.The conjecture is not proved even for short-holed graphs and would imply a singly-exponential χ-bound in terms of ω.
  • Colouring graphs with no long holes: A stronger conjecture would partition every odd-hole-free graph into ω(G) sets, each inducing a perfect graph, implying χ(G) ≤ω(G)^2.This stronger conjecture is attributed to Hoàng.
  • Colouring graphs with no long holes: Forbidding cycles with exactly k chords is conjectured to define a χ-bounded ideal, as is forbidding induced cycles containing a vertex with at least k neighbours on the cycle.Earlier results establish χ-boundedness when cycles with a unique chord, or long cycles with a unique chord, are excluded.
  • Colouring graphs with no long holes: Circle graphs are vertex-minor-closed and polynomially χ-bounded with a quadratic binding function, while recent results culminate in a claim that every proper vertex-minor-closed ideal is χ-bounded.Earlier theorems covered ideals excluding all wheels or all circle graphs; related conjectures concern polynomial-time clique and stable-set algorithms.
  • Algorithms: Even when χ-boundedness is known, the survey asks whether the corresponding colourings can be found in polynomial time.For odd-hole-free graphs, an existing algorithm either finds an odd hole or returns a clique and a colouring using at most doubly-exponentially many colours in the clique size.
Loading 1812.07500v3…