On polynomial degree-boundedness

A class is said to be $\chi$-bounded if the chromatic number of graphs in the class is bounded by a function of their clique number. A classical theorem of Erdős implies that the class of all graphs is not $\chi$-bounded. On the other hand, a number of natural graph classes are $\chi$-bounded (for instance perfect graphs, or intersection graphs of axis-parallel rectangles in the plane, or several other “geometric” graph classes). A number of important conjectures in graph theory are related to $\chi$-boundedness, for instance the Gyárfás-Sumner conjecture and the Erdős-Hajnal conjecture. For the latter conjecture, an important problem is to understand not only which classes of graphs are $\chi$-bounded, but also which are polynomially $\chi$-bounded (i.e., there is a polynomial dependence between the clique and chromatic numbers).

Erdős asked in the 1970s if intersection graphs of segments in the plane are $\chi$-bounded. A negative answer was given by Pawlik, Kozik, Krawczyk, Lasoń, Micek, Trotter, and Walczak in this paper. Their construction also disproved a conjecture of Scott stating that for any graph $H$, the family of graphs which do not contain any subdvision of $H$ as an induced subgraph is $\chi$-bounded. The connection is the following: Consider the graph $H$ obtained by $K_5$, the complete graph on 5 vertices, by subdividing every edge once (i.e. replacing it by a 2-edge-path). Observe that no subdivision of $H$ can be represented as the intersection of segments in the plane, since otherwise we could obtain a planar drawing of $K_5$, which would contradict the non-planarity of $K_5$. So the non $\chi$-bounded segment graphs constructed by Pawlik et al. do not contain any induced subdivision of $H$, and Scott’s conjecture thus fails for this particular graph $H$.

Understanding which graphs $H$ satisfy Scott’s conjecture remains a challenging problem. Scott had originally proved that his conjecture holds whenever $H$ is a tree. In this area, a very convenient tool in proofs is a result of Kühn and Osthus which states that for every graph $H$, a graph $G$ without induced subdivisions of $H$ either contains a large complete bipartite graph as a subgraph, or $G$ has bounded average degree and bounded chromatic number. So we can always start by assuming without loss of generality that our graph $G$ has a very large complete bipartite subgraph, since otherwise we are done already by the second part of the result of Kühn and Osthus. Having a large complete bipartite subgraph can then be the starting point of a more careful analysis of the structure of the graph, from which we ultimately deduce the desired result.

Unfortunately the bound on the average degree in the result of Kühn and Osthus was very large, and thus all applications on $\chi$-boundedness had a very large dependence between the clique and chromatic numbers.

In this paper, the authors prove that the dependence between the average degree and the size of the complete bipartite subgraph in the result of Kühn and Osthus can be taken to be a polynomial. This implies that a number of earlier results which used their theorem now also have a polynomial dependence between the clique and chromatic numbers. In particular it directly implies that graphs without induced subdivisions of the complete bipartite graph $K_{s,t}$ (for fixed $s$ and $t$) are polynomially $\chi$-bounded. This was already open for $K_{2,3}$.