# A survey of degree-boundedness

Xiying Du  School of Mathematics, Georgia Institute of Technology. E-mail:
<EMAIL_ADDRESS>Rose McCarty The second author is supported by the National
Science Foundation under Grant No. DMS-2202961. School of Mathematics and
School of Computer Science, Georgia Institute of Technology. E-mail:
<EMAIL_ADDRESS>
###### Abstract

If a graph has no large balanced bicliques, but has large minimum degree, then
what can we say about its induced subgraphs? This question motivates the study
of degree-boundedness, which is like $\chi$-boundedness but for minimum degree
instead of chromatic number. We survey this area with an eye towards open
problems.

###### Contents

  1. 1 Introduction
  2. 2 What makes a graph dense?
    1. 2.1 Thomassen’s Conjecture
    2. 2.2 Stronger extremal bounds
  3. 3 Connections to $\chi$-boundedness
    1. 3.1 Esperet’s Conjecture
    2. 3.2 Minimum degree and clique number
    3. 3.3 The Erdös-Hajnal Conjecture
    4. 3.4 Direct implications
    5. 3.5 Perfect graphs
    6. 3.6 Induced subdivisions
    7. 3.7 Induced trees
  4. 4 Degree-bounding functions
    1. 4.1 Dichotomy
    2. 4.2 Almost regular graphs
    3. 4.3 Unbalanced bipartite graphs
  5. 5 Examples
    1. 5.1 Convex sets in Euclidean space
    2. 5.2 Circle graphs and vertex-minors
    3. 5.3 String graphs and induced minors
    4. 5.4 Width parameters and a broader trend

##  1 Introduction

Informally, a class of graphs $\mathcal{F}$ is _degree-bounded_ if every graph
in $\mathcal{F}$ with sufficiently large minimum degree has a big balanced
biclique $K_{t,t}$. This intuitively says that for graphs in $\mathcal{F}$,
minimum degree is a “local property”. This is definitely not the case for all
graphs due to a famous random construction of Erdős [49] and lower bounds on
the Kővári-Sós-Turán Theorem [79] on the extremal numbers of bipartite graphs.
In fact, degree-boundedness has many nice connections to extremal graph
theory, and we discuss these in Section 2.

For now though, we focus on what has recently become the standard definition
of degree-boundedness. Given a graph $G$, the _biclique number_ of $G$ is the
largest integer $t$ so that $G$ has a subgraph (not necessarily induced) which
is isomorphic to the biclique $K_{t,t}$. We denote the biclique number of $G$
by $\tau(G)$. Then a class of graphs $\mathcal{F}$ is _degree-bounded_ if
there exists a function $f$ so that each graph $G\in\mathcal{F}$ has a vertex
of degree at most $f(\tau(G))$. (Just to avoid technicalities, we assume
throughout the paper that every graph has at least one vertex.) We write
$\delta(G)$ for the _minimum degree_ of a graph $G$; thus we have
$\delta(G)\leqslant f(\tau(G))$ for every $G\in\mathcal{F}$. Any function $f$
with this property is called a _degree-bounding function_ for $\mathcal{F}$.

Culminating a long line of research [11, 17, 44, 80, 87, 96, 118], Girão and
Hunter [67] recently proved the following surprising theorem. It says that
under a mild assumption about the class $\mathcal{F}$ being _hereditary_ ,
that is, closed under taking induced subgraphs, there must exist a very
efficient degree-bounding function for $\mathcal{F}$.

######  Theorem 1.1 (Girão and Hunter [67]).

Any hereditary, degree-bounded class $\mathcal{F}$ has a degree-bounding
function that is a polynomial.

The theorem is striking because it says that as soon as any bound at all
exists, there is actually a very efficient bound. We discuss how one proves
something like Theoren 1.1 in Section 4.

The definition of degree-boundedness is intentionally chosen to resemble the
definition of $\chi$-boundedness. The study of $\chi$-boundedness has a rich
history, from Vizing’s Theorem [131] about line graphs to the Strong Perfect
Graph Theorem of Chudnovsky, Robertson, Seymour, and Thomas [26]. In general,
$\chi$-boundedness studies when the chromatic number – rather than the minimum
degree – is a “local property”. (The _chromatic number_ of a graph $G$ is
denoted by $\chi(G)$, and it is the minimum number of colors needed to color
the vertices of $G$ so that no pair of adjacent vertices receives the same
color.) Since bicliques do not have large chromatic number, $\chi$-boundedness
instead considers the clique number of a graph $G$. The _clique number_ of $G$
is denoted by $\omega(G)$, and it is the largest integer $t$ so that the
clique $K_{t}$ is a subgraph of $G$. A class of graphs $\mathcal{F}$ is
_$\chi$ -bounded_ if there exists a function $g$ so that every graph
$G\in\mathcal{F}$ has chromatic number at most $g(\omega(G))$. Any such
function is called a _$\chi$ -bounding function_ for $\mathcal{F}$.

So degree-boundedness is like $\chi$-boundedness, but where we study the
minimum degree instead of the chromatic number, and bicliques instead of
cliques. Given the similarity in the definitions, another thing that makes
Theorem 1.1 particularly surprising is that the analogous statement for
$\chi$-boundedness is false. In fact it is very false; Briański, Davies, and
Walczak [19] recently proved that there exists a hereditary, $\chi$-bounded
class whose optimal $\chi$-bounding function grows arbitrarily quickly. This
theorem was a huge step forward in our understanding of $\chi$-boundedness.
Previously, Esperet [51] had conjectured that there must be a $\chi$-bounding
function that is a polynomial, and there was a lot of evidence for this
conjecture. In Section 3, we discuss how Theorem 1.1 is related to Esperet’s
Conjecture, to $\chi$-boundedness, and to another famous conjecture of Erdös
and Hajnal [50]. In fact, there is a reasonably general setting under which
Theorem 1.1 actually recovers Esperet’s Conjeture; see Section 3.2.

Finally, in Section 5 we discuss examples of degree-bounded classes. Many –
but not all – of these classes are also $\chi$-bounded. The examples typically
come from forbidding some substructure, or considering graphs with geometric
representations, or bounding some measure of “width”, or from connections to
finite model theory. The last two cases are conjecturally related via flip-
width, which is a new notion of width introduced by Toruńczyk [130]. Flip-
width generalizes the notion of the cops and robbers game which was used by
Seymour and Thomas [120] to characterize graphs of bounded treewidth. We refer
the reader to [130].

Some illustrative examples of degree-bounded classes are given in the theorem
below.

######  Theorem 1.2 (by [86], Lemma 5.1, [130], and [87, 96], respectively).

If $\mathcal{F}$ is a class of graphs such that any of the following
properties hold, then $\mathcal{F}$ is degree-bounded.

  1. 1.

There exists a graph $H$ so that no graph in $\mathcal{F}$ contains an induced
subdivision of $H$.

  2. 2.

There exists a positive integer $d$ so that every graph in $\mathcal{F}$ is an
intersection graph of a collection of balls in $\mathbb{R}^{d}$.

  3. 3.

The class $\mathcal{F}$ has bounded flip-width.

  4. 4.

There exists an integer $c$ so that no graph in $\mathcal{F}$ has an induced
subgraph which is $4$-cycle free and has minimum degree at least $c$.

Given graphs $G$ and $H$, we say that $G$ is _$H$ -free_ if $G$ has no
subgraph (not necessarily induced) which is isomorphic to $H$. Note that the
sufficient condition from part _4._ of Theorem 1.2 is also necessary; so it
actually characterizes degree bounded classes. This is one of the key facts
which underlies Theorem 1.1, as we will discuss in Section 4.

We hope that this survey paper serves to introduce new researchers to the
exciting area of degree-boundedness. With this goal in mind, we focus on the
state of the art and on future directions of research. We draw attention to a
number of conjectures from other papers (see Conjectures 2.5, 2.12, 3.6, and
3.13), pose open problems (see Problems 2.9, 3.9, 3.10, and 5.2), and propose
new conjectures (Conjectures 2.14, 5.4, and 5.7).

##  2 What makes a graph dense?

Degree-boundedness is motivated by the following question: What are the
unavoidable induced subgraphs in graphs with large minimum degree? In this
section we take a broader approach to this question. In Section 2.1, we
discuss Thomassen’s Conjecture about unavoidable subgraphs, how to generalize
this conjecture to induced subgraphs, and its connections to degree-
boundedness. Then in Section 2.2 we discuss extremal aspects related to the
Kővári-Sós-Turán Theorem [79] about the number of edges in a graph with no
$K_{t,t}$-subgraph. We reinterpret degree-bounded classes as precisely those
classes which satisfy much stronger extremal bounds than normal.

Throughout this section, we freely use the fact that we can go back and forth
between minimum degree and average degree. (The _average degree_ of a graph
$G$ is just the average degree of its vertices, so it is $\sum_{v\in
V(G)}\deg(v)/|V(G)|$.) That is, we will use the fact that having an induced
subgraph of large minimum degree is the same thing as having an induced
subgraph of large average degree. In particular, the following lemma implies
that a hereditary class of graphs $\mathcal{F}$ is degree-bounded if and only
if there exists a function $f$ so that every graph $G\in\mathcal{F}$ has
average degree at most $f(\tau(G))$.

######  Lemma 2.1.

For every $d\in\mathbb{R}$, every graph with minimum degree at least $d$ has
average degree at least $d$, and every graph with average degree at least $d$
has an induced subgraph with minimum degree at least $d/2$.

###### Proof.

The first part of the lemma is obvious, and for the second part of the lemma,
suppose that $G$ is a graph of average degree at least $d$. Let $H$ be an
induced subgraph of $G$ which has as few vertices as possible subject to still
having average degree at least $d$. If $v$ was a vertex of $H$ of degree at
most $d/2$, then the graph $H-v$ would still have average degree at least $d$,
a contradiction to the choice of $H$. ∎

###  2.1 Thomassen’s Conjecture

A classical result of Erdős [49] implies that there exist graphs of
arbitrarily large minimum degree and girth. (The _girth_ of a graph $G$,
denoted by $\textrm{girth}(G)$, is the minimum number of edges in any cycle of
$G$, or $\infty$ if $G$ has no cycles. So a graph has large girth if all of
its cycles are long.) Erdős’ construction is random, so in some sense these
graphs are quite common.

In 1983, Thomassen [127] proposed the following beautiful conjecture, which
says that not only are these graphs common, but they are in fact entirely
unavoidable: they occur inside every graph of sufficiently large minimum
degree.

######  Thomassen’s Conjecture ([127]).

There is a function $f:\mathbb{N}^{2}\rightarrow\mathbb{N}$ so that for any
integers $k$ and $d$, every graph $G$ with $\delta(G)\geqslant f(k,d)$ has a
subgraph $H$ so that $\delta(H)>d$ and $\textrm{girth}(H)>k$.

This conjecture has remained wide open for the last $40$ years. In particular,
it is open when $k=6$. Thomassen’s Conjecture can, however, be reduced to the
case that $G$ is bipartite by applying the following well-known fact.

######  Lemma 2.2.

Every graph $G$ has a bipartite subgraph $H$ which contains at least half of
the edges of $G$.

This lemma can be proven by induction on the number of vertices of $G$, or by
including each vertex in one of the two sides independently at random with
probability $1/2$.

Lemma 2.2 yields the $k=3$ case of Thomassen’s Conjecture, and it shows that
we only care about even $k$. Already the next case when $k=4$ is much more
difficult, and it was proven in 2004 by Kühn and Osthus [85].

######  Theorem 2.3 ([85]).

There is a function $f_{\ref{thm:KO}}:\mathbb{N}\rightarrow\mathbb{N}$ so that
for any integer $d$, every bipartite graph $G$ with $\delta(G)\geqslant
f_{\ref{thm:KO}}(d)$ has a subgraph $H$ with $\delta(H)\geqslant d$ and
without $4$-cycles.

Dellamonica, Koubek, Martin, and Rödl [41] gave another proof of Theorem 2.3
using a theorem of Füredi [60] on $r$-uniform hypergraphs. This theorem of
Füredi can be translated to the setting of bipartite graphs where one side is
$r$-regular, that is, contains only vertices of degree $r$. Essentially,
Füredi’s Theorem gives us some “uniform behavior” for the number of common
neighbors of pairs of vertices on the other side. Montgomery, Pokrovskiy, and
Sudakov [101] also gave another proof of Theorem 2.3, obtaining better
quantitative bounds.

There is not much more known about Thomassen’s Conjecture. It is true for
regular graphs, and for graphs whose maximum degree is not much more than
their average degree, using the original proof of Erdős [49]. That is, we can
find the desired subgraph $H$ of a regular graph $G$ by including each edge of
$G$ independently at random with some probability $p$, and then deleting one
edge from each short cycle. Greatly improving on this result, Dellamonica and
Rödl [42] proved Thomassen’s Conjecture for graphs $G$ whose maximum degree is
at most doubly exponential in a small enough power of their average degree.
There has also been some work on stronger versions of Thomassen’s Conjecture
for expanders, where we can hope to find the desired graph $H$ on the same
vertex-set as $G$; we refer the reader to [7].

Unfortunately, there is an obstruction to all of these approaches that use
regularity; it is not possible to reduce to the case that $G$ is even remotely
regular, due to the following theorem of Pyber, Rödl, and Szemerédi [109] and
its generalizations.

######  Theorem 2.4 ([109]).

There exist bipartite graphs with $n$ vertices and at least
$\Omega(n\log\log(n))$ edges which do not have any $3$-regular subgraph.

Note that, since these graphs are bipartite, they also do not have any
$r$-regular subgraph for any $r\geqslant 3$. The idea of the proof of Theorem
2.4 is to take the union of $\log\log(n)$ random star forests whose high-
degree vertices are all on the same side. In each of the star forests, all of
the high-degree vertices have the same degree, and this degree is very
different for different star forests. Dellamonica, Koubek, Martin, and Rödl
[41, Theorem 17] used a similar construction to show that, for any fixed
integer $\Delta$, there are $n$-vertex graphs with
$\Omega_{\Delta}(n\log\log(n))$ edges that have no subgraph of minimum degree
at least $4$ and maximum degree at most $\Delta$.

It is natural to ask whether Thomassen’s Conjecture holds for _induced_
subgraphs. Here, the answer is clearly no since the clique $K_{t}$ and the
biclique $K_{t,t}$ have no induced subgraph of minimum degree more than $1$
and girth more than $4$. However, the second author conjectures that these are
the only obstructions [96, Conjecture 5].

######  Conjecture 2.5 ([96]).

There is a function $g:\mathbb{N}^{2}\rightarrow\mathbb{N}$ so that for any
integers $k$ and $d$, every graph $G$ with $\delta(G)\geqslant g(k,d)$ has an
induced subgraph $H$ so that either

  * •

$H$ is isomorphic to $K_{d}$,

  * •

$H$ is isomorphic to $K_{d,d}$, or

  * •

$\delta(H)>d$ and $\textrm{girth}(H)>k$.

Conjecture 2.5 implies Thomassen’s Conjecture because large cliques and
bicliques have subgraphs of large minimum degree and girth (because they are
regular, for instance).

Surprisingly, there is almost as much evidence for Conjecture 2.5 as for
Thomassen’s Conjecture. First of all, Conjecture 2.5 can be reduced to the
case that $G$ is bipartite using the following beautiful theorem of Kwan,
Letzter, Sudakov, and Tran [87]. This theorem is the “induced version” of
Lemma 2.2.

######  Theorem 2.6 ([87]).

There is a function $f_{\ref{thm:KLST}}:\mathbb{N}\rightarrow\mathbb{N}$ so
that for any integer $d$, every graph $G$ with $\delta(G)\geqslant
f_{\ref{thm:KLST}}(d)$ has an induced subgraph $H$ so that either

  * •

$H$ is isomorphic to $K_{d}$, or

  * •

$\delta(H)>d$ and $H$ is bipartite.

This theorem proved a conjecture of Esperet, Kang, and Thomassé [52] and
answered a question of Kühn and Osthus [86]. The bounds obtained by Kwan,
Letzter, Sudakov, and Tran [87] are also quite good, but we defer quantitative
aspects until Section 4.

Next, generalizing Theorem 2.3 of Kühn and Osthus [85], the second author [96]
proved the following result, which takes care of the $k=4$ case of Conjecture
2.5.

######  Theorem 2.7 ([96]).

There is a function $f_{\ref{thm:indBip}}:\mathbb{N}\rightarrow\mathbb{N}$ so
that for any integer $d$, every bipartite graph $G$ with $\delta(G)\geqslant
f_{\ref{thm:indBip}}(d)$ has an induced subgraph $H$ so that either

  * •

$H$ is isomorphic to $K_{d,d}$, or

  * •

$\delta(H)>d$ and $H$ has no $4$-cycles.

The proof of Theorem 2.7 follows the ideas of Dellamonica, Koubek, Martin, and
Rödl [41] and also uses Füredi’s Theorem [60] about uniform hypergraphs.

Finally, as was the case for Thomassen’s Conjecture, Conjecture 2.5 also holds
for regular graphs; see [96, Proposition 3]. The proof works the same way as
in the theorem of Erdős [49], except we work with vertices instead of edges.
That is, let us assume that $G$ is a regular graph with large degree and with
no induced subgraph isomorphic to $K_{d}$ or $K_{d,d}$. Then by Ramsey’s
Theorem, there is also an integer $t$ so that $G$ has no subgraph (not
necessarily induced) which is isomorphic to $K_{t,t}$. We form an induced
subgraph $H$ of $G$ by including each vertex independently at random with some
probability $p$, and then deleting one vertex from each short cycle. Since $G$
has no subgraph isomorphic to $K_{t,t}$, we can apply the Kővári-Sós-Turán
Theorem [79], which is stated as Theorem 2.10 in the next subsection. This
theorem bounds the number of edges of a graph with no $K_{t,t}$-subgraph,
which in turn lets us bound the number of short cycles of $G$. This is exactly
what we need for the random construction of $H$ to work.

We note that every known proof of Theorem 2.3 of Kühn and Osthus [85] has some
step where a $K_{t,t}$ subgraph is found. This seems to be the key obstacle in
proving Thomassen’s Conjecture. Conjecture 2.5 suggests that the $k=6$ case is
fundamentally different because there is no “special” induced subgraph like a
clique or a biclique to be found.

So, what is the connection between Thomassen’s Conjecture and degree-
boundedness? It turns out that Theorems 2.6 and 2.7 are equivalent to the
following statement about degree-boundedness.

######  Corollary 2.8.

A hereditary class of graphs $\mathcal{F}$ is degree-bounded if and only if
there exists an integer $c$ so that every bipartite graph $H\in\mathcal{F}$
with no $4$-cycles has $\delta(H)\leqslant c$.

It just takes some unravelling of the definitions to see why Theorems 2.6 and
2.7 imply Corollary 2.8. To see why Corollary 2.8 implies Theorem 2.6, suppose
for a contradiction that there exist graphs of arbitrarily large minimum
degree with no clique $K_{d}$ and no induced bipartite subgraph of minimum
degree greater than $d$. Let $\mathcal{F}$ be the class consisting of all of
these graphs and all of their induced subgraphs. Then there exists an integer
$s$ so that no graph in $\mathcal{F}$ has $K_{s,s}$ as an induced subgraph.
Thus, by Ramsey’s Theorem, there exists an integer $t$ so that no graph in
$\mathcal{F}$ has $K_{t,t}$ as a subgraph (not necessarily induced). So this
class $\mathcal{F}$ is not degree-bounded, and by Corollary 2.8 it contains
bipartite graphs with arbitrarily large minimum degree, a contradiction. The
proof that Corollary 2.8 implies Theorem 2.7 is similar.

Corollary 2.8 provides the intuition for why every degree-bounded class has an
“efficient” degree-bounding function. Essentially, the proofs all show that
this constant $c$ “controls” the rate of growth of an optimal degree-bounding
function. We discuss this more in Section 4.

Let us conclude this section by pointing out an interesting open case of
Corollary 2.5. We say that a graph $G$ is _strongly neighborhood-regular_ if
$G$ is a bipartite graph with bipartition $(A,B)$ so that every vertex in $A$
has the same degree, say $r$, and there exists a partition of $B$ into parts
$B_{1},B_{2},\ldots,B_{r}$ so that

  * •

every vertex in $A$ has exactly one neighbor in each of
$B_{1},B_{2},\ldots,B_{r}$, and

  * •

for each $i\in\\{1,2,\ldots,r\\}$, every vertex in $B_{i}$ has the same
degree, say $d_{i}$, and no two vertices in $B_{i}$ have any common neighbor.

This seems like the key case to study; it might even be possible to use
regularity methods to reduce to something similar. It would be particularly
interesting to know what happens when, informally, $r\ll d_{1}\ll
d_{2}\ll\ldots\ll d_{r}$, that is, when the degrees are very different.

######  Problem 2.9.

Let $G$ be a strongly neighborhood-regular graph with sufficiently high degree
and no $4$-cycles. Does $G$ have an induced subgraph $H$ with $\delta(H)>d$
and no $6$-cycles?

###  2.2 Stronger extremal bounds

A simple corollary of the Kővári-Sós-Turán Theorem [79] is the following
extremal bound on the number of edges in a graph with no subgraph isomorphic
to $K_{t,t}$. (This is essentially equivalent to the Zarankiewicz problem,
however, we state the theorem for general graphs instead of bipartite graphs.
The general case can be reduced to the bipartite case by making a “positive”
and a “negative” copy of each vertex, and replacing each edge $\\{u,v\\}$ by
two edges between the positive and negative copies of $u$ and $v$.)

######  Theorem 2.10 ([79]).

For any integer $t$, every $n$-vertex graph with no subgraph isomorphic to
$K_{t,t}$ has at most $2n^{2-1/t}+tn$ edges.

A key theorem that has come out of the work on degree-boundedness is an
improved version of Theorem 2.10 for classes which forbid a fixed bipartite
graph $H$ as an induced subgraph. Notice that for any hereditary, degree-
bounded class $\mathcal{F}$, there exists an integer $c$ so that no graph in
$\mathcal{F}$ contains an induced subgraph with no $4$-cycle-subgraphs and
with minimum degree at least $c$. So we can take $H$ to be any bipartite graph
that has no $4$-cycle-subgraphs and that has minimum degree at least $c$. For
instance, we can take $H$ to be the incidence graph of a projective plane of
sufficiently large order.

This next theorem was discovered independently by Bourneuf, Bucić, Cook, and
Davies [17, Theorem 1.4] and by Girão and Hunter [67, Lemma 7.1] in connection
to degree-boundedness. A very similar theorem was also proven by Fox, Pach,
Sheffer, Suk, and Zahl [57] when the graph under consideration is bipartite.
This is related to the VC-dimension of a graph, and some nice quantitative
improvements have been made since then; see [59, 77]. Also, this type of
problem was considered by Loh, Tait, Timmons, and Zhou [92], who proved
something similar in the case that $H$ is a biclique.

######  Theorem 2.11 ([17, 67]).

For each bipartite graph $H$, there exists a polynomial $p_{H}$ and a number
$\epsilon_{H}>0$ so that for any integer $t$, every $n$-vertex graph with no
induced subgraph isomorphic to $H$ and no subgraph isomorphic to $K_{t,t}$ has
at most $p_{H}(t)n^{2-\epsilon_{H}}$ edges.

The key improvement in Theorem 2.11 is that the amount saved in the exponent
is fixed for fixed $H$. So when $t$ is large in comparison to $H$, the bound
from Theorem 2.11 is far better than the bound from Theorem 2.10.

For obtaining efficient degree-bounds, it is also very important that $p_{H}$
is a polynomial in $t$. From the extremal perspective, however, it makes sense
to try and optimize $\epsilon_{H}$ while allowing $p_{H}$ to be any function
in $t$. In this direction, Hunter, Milojević, Sudakov, and Tomon [75] proposed
the following intriguing conjecture. Given a graph $H$ and an integer $n$, we
write $\textrm{ex}(n,H)$ for the maximum number of edges in an $n$-vertex
graph with no subgraph (not necessarily induced) that is isomorphic to $H$.

######  Conjecture 2.12 ([75]).

For each bipartite graph $H$, there exists a function $f_{H}$ so that every
$n$-vertex graph with no induced subgraph isomorphic to $H$ and no subgraph
isomorphic to $K_{t,t}$ has at most $f_{H}(t)\cdot\textrm{ex}(n,H)$ edges.

When $H$ is a fixed tree $T$, the extremal number $\textrm{ex}(n,T)$ is
linear, and this conjecture is true precisely because the class of graphs with
no induced subgraph isomorphic to $T$ is degree-bounded (as proven in [80,
118, 75], with better and better bounds). In fact, this approach of looking at
extremal numbers gives us another way to think about degree-boundedness. Given
a class of graphs $\mathcal{F}$ and a graph $H$, we write
$\textrm{ex}_{\mathcal{F}}(n,H)$ for the maximum number of edges in an
$n$-vertex graph in $\mathcal{F}$ that has no subgraph isomorphic to $H$.

######  Observation 2.13.

A class of graphs $\mathcal{F}$ is degree-bounded if and only if
$\textrm{ex}_{\mathcal{F}}(n,K_{t,t})=\mathcal{O}_{t}(n)$ for each fixed
integer $t$.

So, informally, a class is degree-bounded if its extremal numbers are linear
for bipartite graphs. This way of looking at things suggests a more systematic
study of classes which have smaller extremal numbers than normal. There are
many results known in this direction, especially for classes which arise from
discrete geometry and model theory; in addition to the examples discussed
above, see, for instance, [6, 123, 133]. Perhaps most famously, Szemerédi and
Trotter [126] proved that any incidence graph of $n$ points and $n$ lines in
the real plane has $\mathcal{O}(n^{4/3})$ edges. This bound substantially
beats the bound of $\mathcal{O}(n^{3/2})$ which holds for general $n$-vertex
graphs with no subgraph isomorphic to the $4$-cycle $C_{4}$ (see Theorem
2.10). For general graphs that bound is also tight, since incidence graphs of
projective planes have $\Omega(n^{3/2})$ edges.

The work on degree-boundedness suggests the following question. If a
hereditary class of graphs $\mathcal{F}$ satisfies stronger extremal bounds
than normal for $\textrm{ex}_{\mathcal{F}}(n,K_{t,t})$, then does this
“propogate” to better bounds for $\textrm{ex}_{\mathcal{F}}(n,K_{s,s})$ when
$s\geqslant t$? One interesting regime is when the extremal numbers are almost
linear. We say that a class of graphs $\mathcal{F}$ is _almost degree-bounded_
if $\textrm{ex}_{\mathcal{F}}(n,K_{t,t})=n^{1+o_{t}(1)}$ for each fixed
integer $t$. (That is, for each fixed integer $t$, the $o_{t}(1)$ term goes to
zero as $n$ goes to infinity.) Our interest in this case stems primarily from
connections to finite model theory. It is known that monadically dependent
classes of graphs are almost degree-bounded; see [1] and [102, Corollary2.3],
as well as the discussion in Section 5.4. Also, motivated by connections to
model theory, Basit, Chernikov, Starchenko, Tao, and Tran [6] proved that any
class of semilinear bipartite graphs is almost degree-bounded. Improving upon
a special case, Tomon and Zakharov [129] gave a simpler proof that for any
fixed integer $d$, the class of all intersection graphs of axis-parallel boxes
in $\mathbb{R}^{d}$ is almost degree-bounded.

We conjecture that, as in the degree-bounded case, the property of being
almost degree-bounded is “controlled” by the $4$-cycle-free graphs in the
class.

######  Conjecture 2.14.

A hereditary class of graphs $\mathcal{F}$ is almost degree-bounded if and
only if we have $\textrm{ex}_{\mathcal{F}}(n,K_{2,2})=n^{1+o(1)}$.

We hope that this conjecture will also yield a better understanding of the
connections between some of the extremal results discussed in this section.

##  3 Connections to $\chi$-boundedness

In this section we compare and contrast degree-boundedness with
$\chi$-boundedness. We highlight many key parts of the theory of
$\chi$-boundedness as we go, but for a more thorough introduction of
$\chi$-boundedness, we refer the reader to the survey of Scott and Seymour
[116].

We note that there is one direct connection between minimum degree and
chromatic number, which arises from the observation that the greedy algorithm
can be used to color any $d$-degenerate graph with $d+1$ colors. (A graph $G$
is _$d$ -degenerate_ if every induced subgraph of $G$ has minimum degree at
most $d$.) We use this observation a few times in this section.

###  3.1 Esperet’s Conjecture

Polynomial $\chi$-boundedness was a well-known open problem due to Esperet
[51] which has since been resolved in the negative by Briański, Davies, and
Walczak [19]. In this subsection, we discuss Esperet’s Conjecture and how a
theorem of Girão and Hunter [67] on degree-boundedness recovers some aspects
of it.

Esperet’s Conjecture said that, under a mild assumption about the class being
closed under taking induced subgraphs, every $\chi$-bounded class has a very
efficient $\chi$-bounding function.

######  Conjecture 3.1 (conjectured in [51], disproven in [19]).

Every hereditary, $\chi$-bounded class of graphs $\mathcal{F}$ has a
$\chi$-bounding function that is a polynomial.

We call a class of graphs $\mathcal{F}$ _polynomially $\chi$-bounded_ if it
has a $\chi$-bounding function that is a polynomial.

One reason Espseret’s Conjecture garnered a lot of attention is that it
intuitively seems so unlikely to be true. Yet the conjecture remained
tantalizingly open for a number of years, despite many attempts at disproving
it. Again and again, to the surprise of many people working in the area, the
trend seemed to be in favor of Esperet’s Conjecture. First it would be shown
that a class of graphs is $\chi$-bounded. Then, often much later, it would be
shown that the class is indeed polynomially $\chi$-bounded. Examples of this
trend include classes of bounded rank-width [46, 12], classes of bounded twin-
width [14, 108, 18], circle graphs [71, 83, 39, 34], grounded $L$-graphs [98,
38], broom-free graphs [80, 91], and double-star-free graphs [80, 117], for
instance. (Here, we list citations in order of improving $\chi$-bounding
functions.)

Moreover, Esperet’s Conjecture would have implied that every hereditary,
$\chi$-bounded class of graphs $\mathcal{F}$ has the Erdös–Hajnal property. A
class $\mathcal{F}$ _has the Erdös–Hajnal property_ if there exists
$\epsilon>0$ so that every $n$-vertex graph in $\mathcal{F}$ has either a
clique or an independent set of size at least $n^{\epsilon}$. Erdös and Hajnal
[50] conjectured that every class of graphs which is hereditary and does not
contain all graphs (up to isomorphism) satisfies this property. See the survey
by Chudnovsky [25] for a history of this conjecture. Let us just note that
every such class does have much larger cliques or independent sets than normal
[21, 50], and that it is still open whether classes which forbid a path as an
induced subgraph have the Erdös-Hajnal property (even though it is known that
such classes are $\chi$-bounded [72], and there has been a lot of recent
progress [103, 119]). Very recently, Nguyen, Scott, and Seymour [105] proved
that any class of graphs of bounded VC-dimension has the Erdös–Hajnal
property. This theorem applies to a huge number of the graph classes which are
known to be polynomially $\chi$-bounded. However, it does not apply to all of
them – bipartite graphs and their complements are simple examples.

With all of this motivation, it is unfortunate that Esperet’s Conjecture is
false. Also, not only is it false, but it fails in a very strong form. When
they disproved Esperet’s Conjecture, Briański, Davies, and Walczak [19] proved
the following.

######  Theorem 3.2 ([19]).

For any non-decreasing function $f:\mathbb{N}\rightarrow\mathbb{N}$ so that
$f(1)=1$ and $f(n)\geqslant\binom{3n+1}{3}$ for any $n\geqslant 2$, there
exists a hereditary class of graphs $\mathcal{F}$ whose optimal
$\chi$-bounding function is $f$.

That is, for each $n\in\mathbb{N}$, the value $f(n)$ is equal to the maximum
chromatic number of any graph in $\mathcal{F}$ with clique number at most $n$.
So hereditary, $\chi$-bounded classes can have $\chi$-bounding functions that
grow arbitrarily quickly; bounding the value of $f(n)$ does not impose any
bound whatsoever on the value of $f(n+1)$. See also the generalized results in
[66].

The construction used to prove Theorem 3.2 was inspired by a construction of
Carbonero, Hompe, Moore, and Spirkl [23] which was used to prove the following
theorem. (A _triangle_ is just the graph $K_{3}$, so a graph is _triangle-
free_ if it has no three pairwise adjacent vertices.)

######  Theorem 3.3 ([23]).

There exists a hereditary class of graphs $\mathcal{F}$ so that $\mathcal{F}$
is not $\chi$-bounded and every triangle-free graph in $\mathcal{F}$ has
chromatic number at most $4$.

Informally, this theorem says that $f(2)$ does not “control” whether the class
is $\chi$-bounded. We note that in the non-induced setting, it does; Rödl
[112] proved that for every integer $k$, every graph of sufficiently large
chromatic number has a triangle-free subgraph (which is not necessarily
induced) that has chromatic number at least $k$.

In the degree-boundedness setting, informally, it is actually true that $f(2)$
“controls” whether the class is degree-bounded. The corollary discussed in the
last section, Corollary 2.8, immediately implies the following result.

######  Corollary 3.4.

A hereditary class of graphs $\mathcal{F}$ is degree-bounded if and only if
there exists an integer $c$ so that every $4$-cycle-free graph in
$\mathcal{F}$ has chromatic number at most $c$.

As discussed in the last section, this is a corollary of a theorem of Kwan,
Letzter, Sudakov, and Tran [87] combined with a theorem of the second author
[96].

In the case of $\chi$-boundedness, Theorem 3.3 ultimately lead to a disproof
of Esperet’s Conjecture. In a parallel chain of events, Corollary 3.4
ultimately lead to a proof of the degree-boundedness version of Esperet’s
Conjecture. Girão and Hunter [67] proved the following.

See 1.1 Similarly to before, we say a class of graphs $\mathcal{F}$ is
_polynomially degree-bounded_ if $\mathcal{F}$ has a degree-bounding function
that is a polynomial. We note that Theorem 1.1 is essentially tight in that
the degree of the polynomial cannot be uniformly bounded; there are examples
where it must depend on the class $\mathcal{F}$. These examples essentially
come from lower bounds on off-diagonal Ramsey numbers; see [44].

Theorem 1.1 culminated a long line of research. Already in the original proof
of Corollary 3.4 in [87, 96], it was possible to obtain some bound on the rate
of growth of an optimal degree-bounding function. (No bound was actually
stated in [96], but we believe that the proof yielded a bound that was roughly
a tower of $2$’s of height $5$. This is not a particularly impressive bound,
but it already would have shown much different behavior than
$\chi$-boundedness, in light of Theorem 3.2.) With Girão, Hunter, and Scott
[44], the authors then proved that every hereditary degree-bounded class has a
singly exponential degree-bounding function. Finally, in independent work that
was concurrent with the work of Girão and Hunter, the researchers Bourneuf,
Bucić, Cook, and Davies [17] reduced proving Theorem 1.1 to the case of
classes of bipartite graphs. We discuss these results in more detail in
Section 4, focusing on the main ideas that go into proving Theorem 1.1.

###  3.2 Minimum degree and clique number

There is an interesting case where Theorem 1.1 actually does let us recover
Esperet’s Conjecture: hereditary classes where the minimum degree, rather than
the chromatic number, is at most some function of the clique number.

So, let us say that a class of graphs $\mathcal{F}$ is _degree-bounded by
$\omega$_ if there exists a function $f$ such that every graph
$G\in\mathcal{F}$ satisfies $\delta(G)\leqslant f(\omega(G))$. There are many
examples of graph classes which are degree-bounded by $\omega$. By Ramsey’s
Theorem, the class of all graphs with no independent set of size bigger than
$\alpha$ is degree-bounded by $\omega$, for each fixed $\alpha\in\mathbb{N}$.
For a similar reason, for each fixed star $S$, the class of all graphs with no
induced subgraph isomorphic to $S$ is degree-bounded by $\omega$. In fact, it
suffices to say that $V(G)$ can be ordered so that no vertex $v\in V(G)$ has
an independent set of size bigger than $\alpha$ in its _right_ neighborhood.
See [5] and the discussion in [36] for more information about ordered graphs
and $\chi$-boundedness.

There are also many nice geometric examples of graph classes that are degree-
bounded by $\omega$. For each integer $d$, the class of all intersection
graphs of balls in $\mathbb{R}^{d}$ is degree-bounded by $\omega$. (The
_intersection graph_ of a finite collection $\mathcal{B}$ of balls in
$\mathbb{R}^{d}$ is the graph with vertex set $\mathcal{B}$, where two
vertices are adjacent if they have non-empty intersection as balls in
$\mathbb{R}^{d}$.) In fact, this holds if instead of balls we consider compact
convex sets in $\mathbb{R}^{d}$ with bounded aspect ratio, following from work
on separators [74, 100, 122]. Dvořák, Norin, and the second author [47] also
showed that we can allow the aspect ratio to be unbounded as long as for any
pair of shapes $A,B\subseteq\mathbb{R}^{d}$ under consideration, we can
“smoothly slide one of $A,B$ around the interior of the other”. For instance,
we can allow $A$ and $B$ to be axis-aligned rectangles as long as $B$ contains
some translate of $A$ or vice-versa. We note that for all of these examples,
it can actually be shown that the shape of smallest volume has small minimum
degree (as a function of $\omega$).

By combining Theorem 1.1 of Girão and Hunter [67] with well-known bounds on
off-diagonal Ramsey numbers [2], we obtain the following result. Note that by
considering a greedy coloring, Corollary 3.5 implies that every hereditary
class which is degree-bounded by $\omega$ is also polynomially $\chi$-bounded.
This is a special case of Esperet’s Conjecture.

######  Corollary 3.5 ([2, 67]).

Let $\mathcal{F}$ be a hereditary class of graphs which is degree-bounded by
$\omega$. Then there exists a polynomial $p$ so that every graph
$G\in\mathcal{F}$ has $\delta(G)\leqslant p(\omega(G))$.

###### Proof.

First of all, the class $\mathcal{F}$ is degree-bounded since every graph $G$
has $\tau(G)\geqslant\lfloor\omega(G)/2\rfloor$. Thus, by Theorem 1.1, there
exists a polynomial $q$ so that every graph $G\in\mathcal{F}$ has
$\delta(G)\leqslant q(\tau(G))$. We may assume that $q$ is non-decreasing.

Next, notice that there exists a positive integer $s$ so that no graph in
$\mathcal{F}$ has $K_{s,s}$ as an induced subgraph. By applying bounds on off-
diagonal Ramsey numbers [2], there thus exists $\epsilon>0$ so that every
graph $G\in\mathcal{F}$ with biclique number $\tau=\tau(G)$ has a clique of
size $\tau^{\epsilon}$. So, for every graph $G\in\mathcal{F}$, we have
$\omega(G)\geqslant\tau(G)^{\epsilon}$, and thus $\delta(G)\leqslant
q(\tau(G))\leqslant q(\omega(G)^{1/\epsilon})$. So the polynomial
$p(x)=q(x^{\lceil 1/\epsilon\rceil})$ has the desired property. ∎

###  3.3 The Erdös-Hajnal Conjecture

We already discussed the connection between Esperet’s Conjecture and the
Erdös-Hajnal Conjecture in the last subsection. Now let us discuss the
connection between the Erdös-Hajnal Conjecture and Theorem 1.1 about degree-
boundedness.

Given a graph $G$, we define the _induced biclique number of $G$_, denoted
$\widehat{\tau}(G)$, to be the maximum integer $s$ so that $G$ has an induced
subgraph which is isomorphic to either the clique $K_{s}$ or the biclique
$K_{s,s}$. In light of Theorem 1.1, we conjecture the following.

######  Conjecture 3.6.

For any hereditary, degree-bounded class $\mathcal{F}$, there exists a
polynomial $\widehat{p}$ so that every graph $G\in\mathcal{F}$ satisfies
$\delta(G)\leqslant\widehat{p}(\widehat{\tau}(G))$.

Let us note right away that Conjecture 3.6 is actually a special case of the
Erdös-Hajnal Conjecture and so was already conjectured in [50]. In fact, we
now use Theorem 1.1 to argue that Conjecture 3.6 is equivalent to the Erdös-
Hajnal Conjecture for hereditary, degree-bounded classes.

######  Lemma 3.7.

A hereditary, degree-bounded class $\mathcal{F}$ has the Erdös-Hajnal property
if and only if there exists a polynomial $\widehat{p}$ so that every graph
$G\in\mathcal{F}$ satisfies
$\delta(G)\leqslant\widehat{p}(\widehat{\tau}(G))$.

###### Proof.

First, suppose that such a polynomial $\widehat{p}$ exists, and let $d$ be a
number so that $\widehat{p}(x)=\mathcal{O}(x^{d})$. Next, set
$\epsilon=1/(d+1)$, and suppose that $G$ is an $n$-vertex graph in
$\mathcal{F}$ that does not have any clique or independent set of size at
least $n^{\epsilon}$. Then the induced biclique number of $G$ is at most
$n^{\epsilon}$, and thus
$\delta(G)\leqslant\widehat{p}(n^{\epsilon})=\mathcal{O}(n^{\epsilon d})$. As
every induced subgraph of $G$ also has induced biclique number at most
$n^{\epsilon}$, in fact $G$ is $\mathcal{O}(n^{\epsilon d})$-degenerate. Thus
$G$ has an independent set of size at least $n/\mathcal{O}(n^{\epsilon d}+1)$.

Note that, in order to prove that $\mathcal{F}$ has the Erdös-Hajnal property,
it is enough to prove that every $n$-vertex graph in $\mathcal{F}$ has a
clique or an independent set of size $\Omega(n^{\epsilon})$. So we may assume
that $n$ is sufficiently large, and thus

$\displaystyle n/\mathcal{O}(n^{\epsilon d}+1)\geqslant\Omega(n^{1-\epsilon
d})=\Omega(n^{1-d/(d+1)})=\Omega(n^{\epsilon}).$

So indeed, the class $\mathcal{F}$ has the Erdös-Hajnal property.

In the other direction, suppose that $\mathcal{F}$ is a hereditary, degree-
bounded class which has the Erdös-Hajnal property. Let $\epsilon>0$ be such
that every $n$-vertex graph $G\in\mathcal{F}$ has a clique or an independent
set of size at least $n^{\epsilon}$. Then every graph $G\in\mathcal{F}$ with
biclique number $\tau=\tau(G)$ has induced biclique number at least
$\tau^{\epsilon}$, for we can transform each side of the biclique into either
a clique or an independent set of size $\tau^{\epsilon}$. Thus
$\widehat{\tau}(G)\geqslant\tau(G)^{\epsilon}$ for every $G\in\mathcal{F}$.

Now, since $\mathcal{F}$ is hereditary and degree-bounded, by Theorem 1.1
there exists a polynomial $p$ so that every graph $G\in\mathcal{F}$ satisfies
$\delta(G)\leqslant p(\tau(G))$. We may assume that $p$ is non-decreasing.
Then, for every graph $G\in\mathcal{F}$, we have $\delta(G)\leqslant
p(\tau(G))\leqslant p(\widehat{\tau}(G)^{1/\epsilon})$. Thus we can take the
polynomial $\widehat{p}(x)=p(x^{\lceil 1/\epsilon\rceil})$. This completes the
proof of Lemma 3.7. ∎

We recall from the earlier discussion that Nguyen, Scott, and Seymour [105]
recently proved that every class of bounded VC-dimension has the Erdös-Hajnal
Property. This implies Conjecture 3.6 for many interesting cases. They also
proved in [103] that the class of graphs without an induced subgraph
isomorphic to the $5$-vertex path has the Erdös-Hajnal Property. This theorem
resolved a case that had been open for a long time and received a lot of
attention. However, it is still open whether the class of graphs with no
induced subgraph isomorphic to the $6$-vertex path has the Erdös-Hajnal
Property, and this class is degree-bounded by [80]. So Conjecture 3.6 seems
quite difficult.

###  3.4 Direct implications

In this section, we observe that neither $\chi$-boundedness nor degree-
boundedness implies the other, even for hereditary classes. We also propose
some direct connections that could exist. One direction of the claim is
simple; the class of all bipartite graphs is $\chi$-bounded but not degree-
bounded. The other direction, however, is more subtle.

In his PhD thesis, Burling [22] constructed a class of graphs (now called
Burling graphs) which are triangle-free and have arbitrarily large chromatic
number. To begin with, the Burling graph $G_{1}$ is just the graph $K_{2}$,
and one of its vertices is chosen to form a special independent set $I_{1}$ of
$G_{1}$. Then, inductively, given $G_{k}$ and an independent set $I_{k}$ of
$G_{k}$, we form $G_{k+1}$ and $I_{k+1}$ as follows. First, for each vertex
$v\in I_{k}$, we replace $v$ by $|I_{k}|$-many copies of $v$, and then we glue
on a copy $G_{k}^{v}$ of $G_{k}$ to these vertices by identifying them with
the special independent set of $G_{k}^{v}$. Finally, for each $v\in I_{k}$ and
each copy $x$ of $v$, we add two more vertices $x_{1}$ and $x_{2}$. We make
these vertices $x_{1}$ and $x_{2}$ adjacent, and we make $x_{1}$ adjacent to
all of the neighbors of $x$ which are in the original graph $G_{k}$, and we
make $x_{2}$ adjacent to all of the neighbors of $x$ which are in the glued on
copy $G_{k}^{v}$ of $G_{k}$. This graph $G_{k+1}$ is triangle-free, and its
special independent set $I_{k+1}$ consists of all of the vertices $x$ and
$x_{1}$ as defined above.

It can be shown that the chromatic number of the Burling graph $G_{k}$ is more
than $k$. In fact something stronger holds; for any proper coloring of $G_{k}$
with any number of colors, there is a vertex in $I_{k}$ whose neighbors
receive at least $k$ different colors. Suppose we have this for $G_{k}$ and
wish to show it for $G_{k+1}$. The key point is that we can find a vertex
$v\in I_{k}$ and a copy $x$ of $v$ so that at least $k$ different colors
appear in the neighborhood of $x$ within 1) the original graph $G_{k}$ and 2)
within the glued on copy $G_{k}^{v}$ of $G_{k}$. If these two sets of $k$
colors are different, then the vertex $x$ has the desired property. Otherwise,
if they are the same, then the vertex $x_{1}$ has the desired property since
$x_{2}$ receives a new $(k+1)$th color.

Burling graphs are often a source of counterexamples on $\chi$-boundedness,
and this turns out to be the case here as well.

######  Theorem 3.8 (Corollary of [22, 54, 107]).

The class of all graphs $G$ which are an induced subgraph of some Burling
graph is degree-bounded but not $\chi$-bounded.

We already argued that this class is $\chi$-bounded. To see that it is not
degree-bounded, we combine two theorems. First, in order to disprove another
conjecture about $\chi$-boundedness, Pawlik, Kozik, Krawczyk, Lasoń, Micek,
Trotter, and Walczak [107] proved that Burling graphs can be represented by
the intersection pattern of a collection of line segments in the plane. That
is, they proved that for any Burling graph $G_{k}$, there is a collection
$\\{L_{v}:v\in V(G_{k})\\}$ of line-segments in the real plane
$\mathbb{R}^{2}$ so that for any pair of distinct vertices $u,v\in V(G_{k})$,
the vertices $u$ and $v$ are adjacent in $G_{k}$ if and only if the line
segments $L_{v}$ and $L_{u}$ intersect. Second, Fox and Pach [54] proved that
the class of all graphs with such a representation is degree-bounded. (In
fact, they proved this even for the more general class of string graphs which
will be discussed in Subsection 5.1.) Since the class of all graphs with such
a representation is hereditary, Theorem 3.8 follows.

If we wish to save something in this direction, it is natural to ask for the
maximum chromatic number of an $n$-vertex triangle-free graph in a fixed
degree-bounded class. Here we are aiming for a bound that is relatively small
in $n$ rather than constant. In general, every $n$-vertex triangle-free graph
has chromatic number at most $(2+o(1))\sqrt{n/\log(n)}$ [33], and there exist
$n$-vertex triangle-free graphs with chromatic number at least
$(1/\sqrt{2}-o(1))\sqrt{n/\log(n)}$ [9, 53]. It seems possible that in degree-
bounded classes, the answer is significantly lower.

######  Problem 3.9.

Let $\mathcal{F}$ be a hereditary, degree-bounded class. Does every
$n$-vertex, triangle-free graph in $\mathcal{F}$ have chromatic number at most
$n^{o_{\mathcal{F}}(1)}$? What is the best bound?

We write $o_{\mathcal{F}}(1)$ for a function whose limit as $n$ goes to
infinity is $0$, when the class $\mathcal{F}$ is fixed.

The intersection graphs mentioned before – string graphs – satisfy an even
stronger bound. Generalizing work of McGuinness [99], Fox and Pach [56] showed
that every $n$-vertex, triangle-free string graph has chromatic number at most
polylogarithmic in $n$. We note that there is a long history of studying the
maximum chromatic number of $n$-vertex, triangle-free graphs with geometric
representations; see also [58, 124, 132] for other results.

In another direction, we note that maybe the chromatic number is still a
“reasonably local” property in any hereditary degree-bounded class. Let us be
precise. First of all, a class of graphs $\mathcal{F}$ is _$r$ -controlled_ if
there exists a function which bounds the chromatic number of each graph
$G\in\mathcal{F}$ in terms of the maximum chromatic number of any of its
induced subgraphs of radius at most $r$. (The _radius_ of a graph $H$ is the
minimum over all vertices $v\in V(H)$, of the maximum distance between $v$ and
any other vertex of $H$. The _distance_ between two vertices is the minimum
number of edges in any path that joins them.) Thus a hereditary class is
$\chi$-bounded if and only if it is $1$-controlled. While the class of all
string graphs is not $1$-controlled [107], it is $2$-controlled [28]. It would
be nice to have an example of the following.

######  Problem 3.10.

Find a hereditary graph class $\mathcal{F}$ which is degree-bounded but is not
$r$-controlled for any integer $r$.

###  3.5 Perfect graphs

A graph $G$ is _perfect_ if for every induced subgraph $H$ of $G$, the
chromatic number of $H$ is equal to its clique number, that is,
$\chi(H)=\omega(H)$. Berge [8] conjectured a wonderful characterization of
perfect graphs: that a graph is perfect if and only if it does not have an
induced subgraph which is a cycle of length odd and greater than $3$, or the
complement of such a graph. (The _length_ of a cycle is the number of edges it
contains.) Chudnovsky, Robertson, Seymour, and Thomas [26] proved this
conjecture in 2006, for which they won the famous Fulkerson Prize in discrete
mathematics. Their theorem is known as the Strong Perfect Graph Theorem; the
Weak Perfect Graph Theorem is due to Lovász [93] and says that a graph is
perfect if and only if its complement is perfect. Perfect graphs also have
strong connections to combinatorial optimization. They can be used to
characterize when the polytope of a set packing problem has only integral
vertices; see the book by Cornuéjols [31].

In our setting, it is natural to propose the following analog of perfect
graphs. We say that a graph $G$ is _degree-perfect_ if for every induced
subgraph $H$ of $G$, the minimum degree of $H$ is equal to its biclique
number, that is, $\delta(H)=\tau(H)$. Together with the standard
characterization of bipartite graphs, a theorem of Golumbic and Goss [68,
Theorem 4] implies the following characterization of degree-perfect graphs.

######  Theorem 3.11 (Corollary of [68]).

A graph is degree-perfect if and only if it does not have an induced subgraph
which is a cycle of length other than four.

In some ways, the fact that a triangle is not degree-perfect and is thus
forbidden in Theorem 3.11 seems artificial. Perhaps another interesting
characterization could be obtained if, in the definition of degree-perfect
graphs, we replaced $\tau(G)$ by $\max(\tau(G),\omega(G)-1)$, or even by the
maximum minimum degree of a complete multipartite subgraph. Under both of
these definitions cliques would become degree-perfect.

We note that the class of graphs considered in Theorem 3.11 is of independent
interest; they are the “bipartite analog” of chordal graphs. Recall that a
graph is _chordal_ if its only induced cycles are copies of the triangle
$C_{3}$. Theorem 3.11 equivalently says that degree-perfect graphs are
precisely the bipartite graphs whose only induced cycles are copies of the
$4$-cycle $C_{4}$. The theorem of Golumbic and Goss [68, Theorem 4] which
implies Theorem 3.11 says that such graphs have simplicial edges. Simplicial
edges are defined analogously to the simplicial vertices which are studied in
chordal graphs; an edge $e=\\{u,v\\}$ of a bipartite graph $G$ is _simplicial_
if $G$ contains all possible edges between $N(u)$ and $N(v)$. See [68] for
details.

###  3.6 Induced subdivisions

We say that a graph $G$ contains a graph $H$ as an _induced subdivision_ if
there exists an induced subgraph of $G$ which is isomorphic to a subdivision
of $H$. A _subdivision_ of $H$ is any graph which can be obtained from $H$ by
replacing each edge $e=\\{u,v\\}$ of $H$ by a path $P_{e}$ whose ends are $u$
and $v$ and whose internal vertices are all distinct, new vertices. For each
graph $H$, let us write $\mathcal{F}_{H}$ for the class of all graphs which do
not contain $H$ as an induced subdivision.

It was originally conjectured that for every graph $H$, the class
$\mathcal{F}_{H}$ is $\chi$-bounded [114]. This problem has some nice
motivation. First of all, Scott [114] proved that it is true when $H$ is a
tree (that is, that the class $\mathcal{F}_{T}$ is $\chi$-bounded for any tree
$T$). Moreover, one of Gyárfás’ [72] original problems on $\chi$-boundedness
from the 80’s equivalently says that the class $\mathcal{F}_{C}$ is
$\chi$-bounded for any cycle $C$. This conjecture was later proven by
Chudnovsky, Scott, and Seymour [27]. (In fact, with Spirkl [29], they also
showed that it is enough to forbid _odd_ induced subdivisions of a cycle, that
is, where each path $P_{e}$ used to replace an edge $e$ of the cycle has odd
length.)

Overall, however, Pawlik et. al. [107] proved that this conjecture is false by
using the same construction from Theorem 3.8: Burling graphs. This
construction shows that, if $K_{5}^{1}$ denotes the $1$-subdivision of
$K_{5}$, then the class $\mathcal{F}_{K_{5}^{1}}$ is not $\chi$-bounded. (The
_1-subdivision_ of a graph $H$ is the subdivision of $H$ where for every edge
$e=\\{u,v\\}$ of $H$, the path $P_{e}$ which replaces $e$ contains exactly one
additional vertex besides $u$ and $v$.) In fact this construction forbids
induced subdivisions of even more graphs; see [24]. Other positive results
have also been proved, in particular for graphs $H$ which are “banana trees”;
see [28] and [115].

In the case of degree-boundedness, however, the analogous conjecture is
actually true. Kühn and Osthus [86] proved a wonderful theorem which
equivalently says the following.

######  Theorem 3.12 ([86]).

For any graph $H$, the class $\mathcal{F}_{H}$ of all graphs with no induced
subdivision of $H$ is degree-bounded.

Dvořák [45] proved that such classes actually satisfy a much stronger
property. He showed that for any graph $H$, any subclass of $\mathcal{F}_{H}$
with bounded biclique number has not only bounded minimum degree $\delta$, but
in fact also has bounded expansion. We discuss this further in Section 5.4.

Let us also point out that there is a long history of improving the bounds in
Theorem 3.12, that is, of finding efficient degree-bounding functions for
classes with a forbidden induced subdivision. Bonamy, Bousquet, Pilipczuk,
Rzażewski, Thomassé, and Walczak [11] proved that for any path $P$ or cycle
$C$, the classes $\mathcal{F}_{P}$ and $\mathcal{F}_{C}$ are polynomially
degree-bounded. They also conjectured that the class $\mathcal{F}_{H}$ is
polynomially degree-bounded for every graph $H$. Bourneuf, Bucić, Cook, and
Davies [17] proved that the class $\mathcal{F}_{B}$ is polynomially degree-
bounded for any bipartite graph $B$. Finally, Girão and Hunter [67] proved the
full conjecture in an even more general form by proving Theorem 1.1. Overall,
the conjecture on induced subdivisions has motivated much of the work on
degree-boundedness.

We would also like to point the reader towards the following conjecture of
Scott and Seymour [116], which would combine some of the topics discussed
here.

######  Conjecture 3.13 ([116]).

For any graph $H$ and integer $t$, the class of all graphs with no subgraph
isomorphic to $K_{t,t}$ and no induced odd subdivision of $H$ has bounded
chromatic number.

A subdivision of $H$ is _odd_ if for each edge $e\in E(H)$, the path $P_{e}$
used to replace $e$ has odd length. We refer the reader to [116] for a
discussion on the progress towards Conjecture 3.13.

###  3.7 Induced trees

The most famous problem on $\chi$-boundedness which is still open is the
Gyárfás-Sumner Conjecture [70, 125], which proposes that for any forest $T$,
the class of all graphs $G$ with no induced subgraph isomorphic to $T$ is
$\chi$-bounded. (It is known that forests are the only graphs that can have
this property, as there exist graphs of arbitrarily large girth and chromatic
number; see for instance the classical random construction of Erdős [49].)
There is a lot of partial progress on this conjecture; see [116]. Notably,
Gyárfás [72, Theorem 2.4] proved the conjecture for paths using a now famous
path-augmentation argument.

While the Gyárfás-Sumner Conjecture remains open, its degree-bounded analog
has been known for a long time, as discussed in the survey of Scott and
Seymour [116]. First of all, Hajnal and Rödl independently proved that for any
forest $T$ and any integer $t$, the class of all graphs $G$ with no induced
subgraph isomorphic to $T$ and with $\tau(G)\leqslant t$ is $\chi$-bounded;
see [73]. Kierstead and Penrice [80, Corollary 7] then proved a theorem which
implies the following.

######  Theorem 3.14.

[80] For any forest $T$, the class of all graphs with no induced subgraph
isomorphic to $T$ is degree-bounded.

Then, motivated by a question of Bonamy, Bousquet, Pilipczuk, Rzażewski,
Thomassé, and Walczak [11] discussed in the last subsection, Scott, Seymour,
and Spirkl [118] gave a clever argument which shows a polynomial degree-bound.
That is, they showed that for any forest $T$, the class of all graphs with no
induced subgraph isomorphic to $T$ is polynomially degree-bounded. Hunter,
Milojević, Sudakov, and Tomon [75] further improved this result by showing
that there is a degree-bounding function whose degree is linear in the number
of vertices of $T$. So for trees, things are rather well-understood in the
setting of degree-boundedness.

##  4 Degree-bounding functions

In this section, we discuss the rate of growth of optimal degree bounding
functions. As mentioned before, in contrast to $\chi$-boundedness, every
hereditary degree-bounded class $\mathcal{F}$ has a degree-bounding function
that is a polynomial. In this section we give a broad overview of how to prove
this sort of theorem.

The key idea is that the minimum degree of the $4$-cycle free graphs in the
class “controls” the rate of growth of the whole function. Throughout this
section, we let $\mathcal{F}$ denote an arbitrary hereditary degree-bounded
class. Recall from Lemma 2.1 that bounding the minimum degree is the same
thing as bounding the average degree. Thus, there exists an integer
$k:=k({\mathcal{F}})$ such that every $4$-cycle-free graph in $\mathcal{F}$
has average degree less than $k$. The authors, together with Girão, Hunter,
and Scott [44], proved that every hereditary degree-bounded class has a degree
bounding function that is singly exponential in the biclique number $\tau$.

######  Theorem 4.1.

[44] There exists a universal constant $C$ so that $f_{k}(\tau)=k^{C\tau^{3}}$
is a degree-bounding function for any hereditary degree-bounded class
$\mathcal{F}$.

The broad-level approach used to prove Theorem 4.1 remains the same in the
later proofs which obtained better bounds. So let us briefly discuss the key
improvements.

Bourneuf, Bucić, Cook, and Davies [17] reduced polynomial degree-boundedness
to the case of bipartite graphs, and they proved a wonderful strengthening of
the Kővári-Sós-Turán Theorem [79]. The Kővári-Sós-Turán Theorem is a key tool
in all known proofs, and this improvement is a key advancement of Bourneuf,
Bucić, Cook, and Davies. Simultaneously, Girão and Hunter [67] independently
discovered the same key tool. They used this tool, along with some wonderful
lemmas they proved about VC-dimension of a similar flavor to the Sauer-Shelah
Lemma [113, 121], to prove the following degree-bounding function that is
polynomial in $\tau$.

######  Theorem 4.2 ([67]).

There exists a universal constant $C$ so that $p_{k}(s)=\tau^{Ck^{4}}$ is a
degree-bounding function for any hereditary degree-bounded class
$\mathcal{F}$.

In the next few subsections, we discuss the main parts of the proof at a high
level.

###  4.1 Dichotomy

Consider a graph $G$ in $\mathcal{F}$ with biclique number $\tau$ whose
average degree exceeds the desired degree bound. If we are aiming for the
degree bound of $d$, then we may assume that the graph $G$ is roughly
$d$-degenerate, since otherwise we could instead consider a smaller induced
subgraph of $G$ whose average degree still exceeds the bound. The proofs of
all the three mentioned results aim for finding a $4$-cycle-free induced
subgraph of $G$ with average degree at least $k$, which leads to a
contradiction as $\mathcal{F}$ is hereditary. Given that $G$ has large average
degree, the problem can be separated into the following two cases:

  * (A)

$G$ contains an induced subgraph that is “almost regular” and has large
degree, or

  * (B)

$G$ contains an induced bipartite subgraph with sides $A$ and $B$ such that
$|A|$ is much greater than $|B|$ and every vertex in $A$ has large degree.

The general approach to prove the above was already used earlier by Kwan,
Letzter, Sudakov, and Tran [87]. One of the improvements made in [44] was to
use an approach of Montgomery, Pokrovskiy, and Sudakov [101] to “bump” how
large $A$ is in comparison to $B$. So there is an intermediate step where a
“biregular” graph of large average degree is found; this in turn guarantees
the existence of an “almost regular” induced subgraph of large degree; see
[78, Lemma 3.7] in a paper of Janzer and Sudakov which resolved the Erdős-
Sauer problem.

Since this type of dichotomy is (at least at a broad level) a common element
of all of the approaches, we focus instead on the key new improvements of
Bourneuf, Bucić, Cook, and Davies [17], and of Girão and Hunter [67] which
were used to take care of the two cases. Subsections 4.2 and 4.3 are devoted
to introducing the techniques used to handle the two respective cases. Here is
a more rigorous statement of the type of dichotomy theorem that is often used.
Note that in case (B), the graph is not bipartite yet. This can be dealt with
later on using degeneracy.

######  Theorem 4.3.

[44, Lemma 3.4] Let $L,d\geqslant 16$ be positive numbers. Then for any
$n$-vertex graph $G$ with average degree $d$ that is $d$-degenerate, either:

  * (A)

$G$ has an induced subgraph $G_{0}$ with average degree $d_{0}$ at least
$\Omega(d/\log^{2}(L))$ and maximum degree $\Delta_{0}$ at most
$O(d_{0}\cdot\log^{2}(L))$, or

  * (B)

the vertex set of $G$ admits a partition $V(G)=A\sqcup B$ such that
$|A|\geqslant L|B|$ and the number of edges between $A$ and $B$ is at least
$nd/8.$

###  4.2 Almost regular graphs

In all of the mentioned proofs, Case (A) is resolved using variants of the
Kővári-Sós-Turán Theorem. Recall the following statement mentioned in Section
2.2.

See 2.11

In fact, Girão and Hunter [67, Lemma 7.1] proved that when $t$ is sufficiently
large in comparison to the number of vertices of $H$, that we can take
$\epsilon_{H}=1/(100\cdot\Delta(H))$. The following lemma, also proven by
Girão and Hunter, gives a good choice of the graph $H$. For any integers
$\ell$ and $r$ with $r\leqslant\ell$, we write $K_{\ell}^{(r)}$ for the
bipartite graph with $\ell$ vertices on one side and $\binom{\ell}{r}$
vertices on the other side, where for each $r$-subset of the $\ell$ vertices,
there exists a vertex whose neighborhood is precisely that $r$-set. (An _$r$
-set_ is just a set of size $r$.)

######  Lemma 4.4 ([67, Lemma 7.4]).

For each integer $k\geqslant 2$, there exists a $4$-cycle-free bipartite graph
$H=H(k)$ which has at most $8k^{2}$ vertices, has maximum degree at most $2k$,
has average degree at least $k$, and is an induced subgraph of
$K_{8k^{2}}^{(2k)}$.

We may assume that $k\geqslant 2$. So let us now fix a graph $H$ as above. Let
$\epsilon_{H}$ and $p_{H}(t)$ be as in Theorem 2.11. In fact, as mentioned
before, we can take $\epsilon_{H}=1/(100\cdot\Delta(H))\geqslant 1/(200k)$. So
$\epsilon_{H}$ is even relatively large. Note that $H$ is not an induced
subgraph of any graph in $\mathcal{F}$, and so we may apply Theorem 2.11 to
such graphs. We suppose that case (A) of the dichotomy theorem (Theorem 4.3)
holds. Thus, $G_{0}$ is a graph in $\mathcal{F}$ which has average degree
$d_{0}$ at least $\Omega(d/\log^{2}(L))$ and maximum degree $\Delta_{0}$ at
most $O(d_{0}\cdot\log^{2}(L))$. We let $t$ be the smallest integer so that
$G_{0}$ has no induced subgraph isomorphic to $K_{t,t}$. When this dichotomy
theorem is applied, we will have that $\log^{2}(L)$ is still fairly small in
comparison to $d$. So the maximum degree will be not too much larger than the
average degree.

The proof proceeds by finding an induced subgraph of $G_{0}$ by including
vertices independently at random with some probability $q$ and then deleting
the vertices in any $4$-cycle. The resulting graph will be $4$-cycle-free and
will, in expectation, have average degree more than $k$. In this manner we
obtain a contradiction. The key observation is that Theorem 2.11 can be used
to obtain a rather efficient bound on the number of $4$-cycles. The point is
that for every edge $xy\in E(G_{0})$, by applying Theorem 2.11 to the subgraph
of $G_{0}$ induced on the neighbors of $x$ and $y$, we know there are at most
$8p_{H}(t)\Delta_{0}^{2-\epsilon_{H}}$-many 4-cycles containing the edge $xy$
in $G_{0}$. This is the main idea and turns out to be enough for the proof to
go through.

###  4.3 Unbalanced bipartite graphs

Suppose now that case (B) in Theorem 4.3 holds, that is, there exists a
partition $V(G)=A\sqcup B$ such that $|A|\geqslant L|B|$ and the number of
edges between $A$ and $B$ is at least $nd/8$.

An argument using the $d$-degeneracy of $G$ shows that at least $|A|/20$
vertices in $A$ have at least $d/20$ and at most $10d$ neighbors in $B$; among
those vertices, since $G$ is $d$-degenerate, there exists an independent
subset $A_{0}$ of size $|A_{0}|\geqslant(|A|/20)/(d+1)\geqslant|A|/40d$. We
then pass to the induced subgraph $G_{0}$ of $G$ which has vertex-set
$A_{0}\cup B$, where $|A_{0}|>\frac{L}{40d}|B|$, $A_{0}$ is independent in
$G_{0}$, and every vertex in $A_{0}$ has degree between $d/20$ and $10d$ in
the graph $G_{0}$.

Before continuing with the proof sketch of the polynomial bound, we briefly
mention the different technique used in the proof of the singly exponential
bound (Theorem 4.1), and reveal the choice of $L$. The proof of Theorem 4.1
applies the dichotomy with $L=2^{d^{\delta}}$, where $\delta=1/200t$. A
probabilistic argument similar to the one in Subsection 4.2 resolves Case (A)
by applying the classical extremal bound from the Kővári-Sós-Turán Theorem[44,
Lemma 3.3]. For Case (B), the proof is done by first passing to an induced
bipartite graph $G[A^{\prime}\cup B^{\prime}]$ where $A^{\prime}\subset
A,B^{\prime}\subset B$ are independent and every vertex in $A^{\prime}$ has
the same degree, and then applying Füredi’s result to find an induced
$4$-cycle-free subgraph with average degree at least $k$ in it[44, Theorem
5.1].

In the proof of the Theorem 4.2, the dichotomy is performed with $L:=d^{D+3}$,
where $D$ is an integer such that every $K_{k,k}$-free graph in $\mathcal{F}$
has average degree less than $D$, which exists because $\mathcal{F}$ is degree
bounded. The proof sketch in Subsection 4.2 for case (A) goes through as
$d_{0}=\Omega(d/\log^{2}(L))\geqslant{O}(d^{1/2})$ and
$\Delta/d_{0}=O((\log^{2}(L))=O((D\log(d))^{2})\leqslant{O}(d_{0}^{1/1000k})$,
when $d$ is large enough.

We say that a collection $\mathcal{S}$ of subsets of some ground set, in our
case the set of vertices $B$, _$k$ -shatters_ a set $R\subseteq B$ if for
every $k$-subset $S\subseteq R$, there exists a set in $\mathcal{S}$ whose
intersection with $R$ is precisely $S$. Given the graph $G_{0}$, consider a
vertex $x\in A_{0}$. For any independent subset $J$ contained in the
neighborhood of $x$, if the collection $\\{N(x^{\prime})\cap N(x):x\in
A_{0}\setminus\\{x\\}\\}$ $2k$-shatters a $8k^{2}$-subset of $J$, then $G_{0}$
contains the graph $K_{8k^{2}}^{(2k)}$ as desired.

The proof utilizes the following “shattering lemma". The idea is to apply this
lemma within independent sets contained in the neighborhood of vertices $x$.
If the lemma does not apply, then instead we find an induced subgraph where
certain pairs of vertices have few common neighbors. This will also let us
remove all big bicliques and find another win.

######  Lemma 4.5.

[67, Lemma 8.4] Let $D,t\geqslant 2$ and $h$ be integers. Then there exists
$\delta>0$ such that the following holds when $n$ is large enough. For any
collection $\mathcal{S}$ of subsets of $\\{1,2,\ldots,n\\}$ with $F<\delta n$
for all $F\in\mathcal{S}$, if $\mathcal{S}$ does not $t$-shatter an $h$-subset
of $\\{1,2,\ldots,n\\}$, then there exists $I\subseteq\\{1,2,\ldots,n\\}$ with
$|I|=D$ such that $|I\cap S|<k$ for all $S\in\mathcal{S}$.

By arguments similar to case (A), one can prove that we can find large
independent sets in the neighborhood of each vertex. The proof is finished by
using a probabilistic argument to reduce from having relatively few common
neighbors among independent sets within the neighborhoods of vertices to
actually being $K_{k,k}$-free while still having average degree at least $D$.
This broad overview outlines some of the improvements used to obtain a
polynomial degree-bounding function.

##  5 Examples

We have already seen a number of examples of degree-bounded classes in Section
3, where we discussed connections to $\chi$-boundedness. These examples
included:

  * •

classes with bounded independence number [2] (see Subsection 3.2),

  * •

intersection graphs of compact convex sets in $\mathbb{R}^{d}$ of bounded
aspect ratio [74, 100, 122], and some of their generalizations [47] (see
Subsection 3.2),

  * •

intersection graphs of line segments in the plane [54] (see Subsection 3.4),

  * •

the bipartite analog of chordal graphs [68] (see Subsection 3.5),

  * •

classes which forbid induced subdivisions of a fixed graph [86] (see
Subsection 3.6), and

  * •

classes which forbid a fixed tree as an induced subgraph [80] (see Subsection
3.7).

In this section we focus on two types of examples: classes with nice geometric
representations, and classes with bounded width. Many examples of
geometrically-defined classes of graphs that are degree-bounded come from
intersection graphs, and those are the ones that we focus on here. We note
that, additionally, it is open whether the class of curve visibility graphs is
degree-bounded; see [37] for the definition of this class. The subclass of
terrain visibility graphs is degree-bounded due to connections with twin-
width; see [13]. The case of visibility graphs is particularly interesting
because they contain an induced subdivision of every graph, but there are many
more geometric examples one could consider.

We begin by stating the general definitions for intersection graphs. Given a
collection $\mathcal{B}$ of subsets of some ground set $S$, the _intersection
graph of $\mathcal{B}$_ is the graph with vertex set $\mathcal{B}$ where two
vertices are adjacent if they have non-empty intersection as subsets of $S$.
We write $G(\mathcal{B})$ for the intersection graph of $\mathcal{B}$. We
generally require that $\mathcal{B}$ – and thus the graph $G(\mathcal{B})$ –
is finite, but we impose no restrictions on $S$.

We note that every graph $G$ is an intersection graph of a collection of
subsets of $V(G)$. For each vertex $v$ of $G$, let $B_{v}\subseteq V(G)$ be
the set containing $v$ and all of its neighbors. Then two vertices $u$ and $v$
are adjacent in $G$ if and only if $B_{u}$ and $B_{v}$ intersect. (We say that
two sets _intersect_ if their intersection is non-empty.) So in order to
obtain a class of graphs that is degree-bounded, we need to impose some
structure on how sets in $\mathcal{B}$ can intersect. We discuss a number of
ways to use geometry to impose this structure.

###  5.1 Convex sets in Euclidean space

For our first example of geometric intersection graphs, let the ground set be
$S=\mathbb{R}^{d}$, and let $\mathcal{B}$ be any collection of balls in
$\mathbb{R}^{d}$. That is, for each element $B\in\mathcal{B}$, there is a
center point $p\in\mathbb{R}^{d}$ and a radius $r\in\mathbb{R}_{>0}$ so that
$B=\\{x\in\mathbb{R}^{d}:\lVert x-p\rVert_{2}\leqslant r\\}$. A graph $G$ is
an _intersection graph of balls in $\mathbb{R}^{d}$_ if there exists such a
collection $\mathcal{B}$ so that $G$ is isomorphic to the intersection graph
$G(\mathcal{B})$. Characterizing these graphs and determining how dense they
can be has a long and fascinating history. For one rich example, we refer the
reader to the expository article by Cohn [30] for more information about the
density of sphere packings.

As for the characterization problem, there is a famous theorem of Koebe [81]
(also discovered independently by Andreev [4] and Thurston [128]) which
characterizes the intersection graphs of internally disjoint balls in the
plane. A collection $\mathcal{B}$ of balls in $\mathbb{R}^{d}$ is _internally
disjoint_ if the interiors of the balls in $\mathcal{B}$ are pairwise
disjoint.

######  Circle Packing Theorem ([4, 81, 128]).

A graph $G$ is the intersection graph of a collection of internally disjoint
balls in the plane if and only if $G$ is planar.

We also refer the reader to the proof of Brightwell and Scheinerman [20],
which is stated in accessible language and finds a similtaneous representation
of the planar dual.

It is a well-known corollary of Euler’s formula for planar graphs that every
planar graph has a vertex of degree at most $5$. This type of formula can be
roughly generalized to arbitrary intersection graphs of balls in
$\mathbb{R}^{d}$ as follows. First, we say that a collection $\mathcal{B}$ of
subsets of a ground set $S$ is _$k$ -thin_ if every point in $S$ is in at most
$k$ elements of $\mathcal{B}$. Note that if the clique number of
$G(\mathcal{B})$ is at most $k$, then $\mathcal{B}$ is $k$-thin, but not
necessarily vice-versa. Moreover, notice that every collection of internally
disjoint balls in the plane is $2$-thin.

Thus the following lemma is connected both to degree-boundedness and to the
minimum degree of planar graphs. In particular, the lemma implies that for any
fixed $d$, the class of intersection graphs of balls in $\mathbb{R}^{d}$ is
degree-bounded by the linear function $f_{d}(\tau)=(2\tau+1)2^{d}$. This lemma
is well-known, but since the proof is short, we provide it anyways.

######  Lemma 5.1.

For any positive integers $k$ and $d$ and any finite $k$-thin collection
$\mathcal{B}$ of balls in $\mathbb{R}^{d}$, the intersection graph
$G(\mathcal{B})$ has a vertex of degree less than $k\cdot 2^{d}$.

###### Proof.

Let $B\in\mathcal{B}$ be a ball of minimum volume; we will show that $B$ is
the desired vertex of small degree. By translating and then scaling, we may
assume that $B$ is the unit ball centered at the origin, that is,
$B=\\{x\in\mathbb{R}^{d}:\lVert x\rVert_{2}\leqslant 1\\}$. (A _unit ball_ is
any ball of radius $1$.) Now note that for any
$B^{\prime}\in\mathcal{B}\setminus\\{B\\}$ which intersects $B$, there exists
a unit ball which is contained in $B^{\prime}$ and still intersects $B$. Thus,
there exists a $k$-thin collection $\mathcal{B}^{\prime}$ of unit balls so
that 1) the degree of $B$ in the intersection graph $G(\mathcal{B})$ is less
than $|\mathcal{B}^{\prime}|$, and 2) every ball in $\mathcal{B}^{\prime}$ is
a subset of the ball of radius $2$ centered at the origin.

Let us write $v_{d}$ for the volume of a unit ball in $\mathbb{R}^{d}$. It
follows from the definition of $\mathcal{B}^{\prime}$ that the sum of the
volumes of the balls in $\mathcal{B}^{\prime}$ is
$v_{d}|\mathcal{B}^{\prime}|$, and that this sum is at most $k(v_{d}\cdot
2^{d})$ since $v_{d}\cdot 2^{d}$ is the volume of a ball of radius $2$. So
$|\mathcal{B}^{\prime}|\leqslant k\cdot 2^{d}$, and the lemma follows. ∎

It is an interesting but likely very difficult question to find the optimal
constant which can replace $2^{d}$ in Lemma 5.1. While there are many ways to
formulate this problem, let us pose the following version.

######  Problem 5.2.

For each fixed integer $d$, determine the smallest integer $c_{d}$ so that
every finite $k$-thin collection $\mathcal{B}$ of balls in $\mathbb{R}^{d}$
contains a ball which intersects at most $c_{d}k+o_{d}(1)$ balls in
$\mathcal{B}$.

While we do not know of any direct reduction, this problem seems highly
related to the famous question about the density of sphere packings; see [30].

We also note that a similar argument to the one in Lemma 5.1 works for
intersection graphs of compact convex sets in $\mathbb{R}^{d}$ of bounded
aspect ratio. (The _aspect ratio_ of a compact convex set is its diameter
divided by its height; the _diameter_ is the largest distance between two
parallel hyperplanes which “surround” the set, and the _height_ is the
smallest such distance.) There are also more sophisticated arguments that such
intersection graphs are degree-bounded due to the existence of small
separators [74, 100, 122]. Dvořák, Norin, and the second author [47] also
found a more general geometric condition that guarantees the existence of
small separators and thus a vertex of small degree. The proof works by sorting
the shapes by their volume, so it could also be used to show that any shape of
minimum volume is a low-degree vertex.

###  5.2 Circle graphs and vertex-minors

A _chord_ of a circle is a (closed) line segment with ends on the circle. Let
us consider intersection graphs of a (finite) collection of chords on the unit
circle; any such graph is called a _circle graph_. More precisely, a graph $G$
is a _circle graph_ if there exists a collection $\mathcal{C}$ of chords on
the unit circle $\\{(x,y)\in\mathbb{R}^{2}:x^{2}+y^{2}=1\\}$ so that $G$ is
isomorphic to the intersection graph $G(\mathcal{C})$.

Fox and Pach [54] proved that the class of all circle graphs is linearly
degree-bounded, that is, that the following bound holds.

######  Theorem 5.3 ([54]).

There exists a constant $c$ so that every circle graph $G$ has a vertex of
degree at most $c\cdot\tau(G)$.

In fact, Fox and Pach proved this theorem in much more generality; they showed
that it holds 1) for intersection graphs of line segments in the plane, and 2)
for intersection graphs of collections of strings in the plane so that every
pair of strings intersects at most $t$ times. (The constant $c$ depends on
$t$.) A _string_ is a homeomorphic image of the interval $[0,1]$ in the plane.
We will discuss strings more in the next subsection.

The reason why we are discussing circle graphs in particular is related to a
more general question about classes of graphs with a forbidden vertex-minor. A
_vertex-minor_ of a graph $G$ is any graph that can be obtained from $G$ by
taking induced subgraphs and by performing certain local moves at vertices
called local complementations. _Locally complementing_ at a vertex $v$ of a
graph $G$ replaces the induced subgraph on the neighborhood of $v$ by its
complement. That is, it exchanges edges/non-edges between any pair of vertices
$x,y\neq v$ which are adjacent to $v$.

The class of circle graphs is closed under taking vertex-minors, and Bouchet
[16] found the forbidden vertex-minors: there are only three of them.
Surprisingly, this theorem is related to the famous theorem of Kuratowski and
Menger about the forbidden minors for planar graphs. The connection was
discovered by de Fraysseix [40], and Geelen and Oum [64] have proven a common
generalization of the two theorems. Motivated by a structural question of
Geelen about classes of graphs which forbid a vertex-minor (see the second
author’s thesis for a formal statement of the conjecture [97]), we conjecture
the following.

######  Conjecture 5.4.

For any graph $H$, there exists a constant $c=c(H)$ so that every graph $G$
with no vertex-minor isomorphic to $H$ contains a vertex of degree at most
$c\cdot\tau(G)$.

The conjecture says that for any graph $H$, the class of all graphs with no
vertex-minor isomorphic to $H$ is linearly degree-bounded. Such classes are
known to be degree-bounded by a theorem of Kühn and Osthus [86] (which is
stated as Theorem 3.12 in this paper). So Conjecture 5.4 is really about
obtaining an optimal bound; even just a bound where the degree of the
polynomial does not depend on $H$ would be interesting. We note that Davies
proved that classes with a forbidden vertex-minor are $\chi$-bounded [35], and
that Conjecture 5.4 holds when $H$ is a circle graph by combining results in
[63, 69, 106].

###  5.3 String graphs and induced minors

A _string_ is a continuous arc in the plane, and a _string graph_ is any graph
which is isomorphic to the intersection graph $G(\mathcal{S})$ of some finite
collection $\mathcal{S}$ of strings. Such graphs have a long history, and we
refer the reader to the survey of Matoušek [95] for more background.

For our purposes, string graphs are interesting because classes of string
graphs which forbid a biclique as a subgraph behave a lot like planar graphs.
In particular, they satisfy a separator theorem which generalizes the original
separator theorem for planar graphs of Lipton and Tarjan [90]. This theorem
was conjectured by Fox and Pach [54], and Matoušek [94] proved a slightly
weaker version with an extra $\log(m)$ factor. (The theorem of Matoušek would
have already been strong enough for our applications.) The stronger version
stated here was proven by Lee [88]. A _balanced separator_ in a graph $G$ is a
subset $X\subseteq V(G)$ so that once $X$ is deleted from $G$, every remaining
component has at most $2|V(G)|/3$ vertices. (The fraction $2/3$ is not too
important and can often be replaced by any fixed positive number less than
$1$.)

######  Theorem 5.5 ([88]).

There exists a constant $c$ so that every string graph with $m$ edges has a
balanced separator of size at most $c\sqrt{m}$.

Theorem 5.5 implies that the class of string graphs is degree-bounded. This
implication can be obtained by using the Kővári-Sós-Turán Theorem [79] and the
fact that every graph class with (strongly) sublinear separators actually has
polynomial expansion, which was proven by Dvořák and Norin [48]. However, a
much more direct proof is given by Fox and Pach in [56, Theorem 5]. As noted
by Lee [88], the proof of Fox and Pach implies the following bound.

######  Theorem 5.6 ([88]).

There exists a constant $c$ so that every string graph $G$ has a vertex of
degree at most $c\cdot\tau(G)\log(\tau(G))$.

The separator theorem of Lee [88] applies to much more general classes of
graphs. First of all, a _minor_ of a graph $G$ is any graph that can be
obtained from $G$ by a sequence of vertex-deletions, edge-deletions, and edge-
contractions. An _induced minor_ of $G$ is any graph that can be obtained from
$G$ by just a sequence of vertex-deletions and edge-contractions (so edge-
deletions are not allowed). Graph minors are very well-understood; the famous
Graph Minors Theorem of Robertson and Seymour [111] says that any class of
graphs which is closed under taking minors has only finitely many excluded
minors. Induced minors have been studied much less, but there has been a
resurgence recently due to connections with metric geometry; see [3, 10, 65,
104]. Notably, the class of string graphs is closed under taking induced
minors, and yet Kratochvíl [84] proved that it is NP-hard to determine if a
graph is a string graph. This theorem shows that induced minors are much
harder to deal with than graph minors. Every minor-closed class can be
recognized in polynomial time due to the Graph Minors Theorem and algorithms
for testing for a fixed graph $H$ as a minor [110].

We note that Lee [88] actually proved a separator theorem like Theorem 5.5 for
any class of intersection graphs which come from a proper minor-closed class.
(A class of graphs $\mathcal{F}$ is _proper_ if there exists a graph which is
not isomorphic to any graph in $\mathcal{F}$.) Given a class of graphs
$\mathcal{F}$, we write $int(\mathcal{F})$ for the class of all graphs $G$ so
that there exists a graph $\widehat{G}\in\mathcal{F}$ and a collection
$\mathcal{C}$ of subsets of $V(\widehat{G})$ so that each set in $\mathcal{C}$
induces a connected subgraph of $\widehat{G}$, and so that $G$ is isomorphic
to the intersection graph $G(\mathcal{C})$. It turns out that the class of all
string graphs is precisely $int(\mathcal{F}_{planar})$, where
$\mathcal{F}_{planar}$ denotes the class of all planar graphs; see [88]. In
general, if $\mathcal{F}$ is any proper minor-closed class, then
$int(\mathcal{F})$ is a proper induced-minor-closed class. Lee [88] proved
that any class of the form $int(\mathcal{F})$, where $\mathcal{F}$ is a proper
minor-closed class, satisfies a separator theorem like Theorem 5.5.

This theorem of Lee implies that any such class $int(\mathcal{F})$ is degree-
bounded. However, we actually already knew that by Theorem 3.12 of Kühn and
Osthus [86] (because for any graph $H$, every induced subdivision of $H$
contains $H$ as an induced minor). However, we conjecture that something even
stronger holds for classes of the form $int(\mathcal{F})$; we believe that
there should be a uniform bound on the rate of growth of their degree-bounding
functions. Perhaps this bound is even the same as in Theorem 5.6.

######  Conjecture 5.7.

For any proper minor-closed class of graphs $\mathcal{F}$, there exists a
constant $c=c(\mathcal{F})$ so that every graph $G\in int(\mathcal{F})$ has a
vertex of degree at most $c\cdot\tau(G)\log(\tau(G))$.

In fact, it seems that the only missing piece is a generalization of [56,
Lemma 1.7], which was originally proven in another paper by Fox and Pach [55].

Finally, we note that Korhonen and Lokshtanov [82] recently generalized the
separator theorem even further, to any proper induced-minor-closed class.
However, we believe that Conjecture 5.7 does not hold for arbitrary proper
induced-minor-closed classes. This is due to the fact that classes of graphs
with bounded independence number are actually closed under taking induced
minors. This example was pointed out by Korhonen and Lokshtanov as one that
does not seem to be contained in $int(\mathcal{F})$ for any proper minor-
closed class $\mathcal{F}$.

###  5.4 Width parameters and a broader trend

As pointed out in Theorem 1.2, every graph class of bounded flip-width is
degree-bounded due to a theorem of Toruńczyk [130]. This theorem implies that
every class of bounded clique-width or bounded twin-width is degree-bounded,
simply because such classes have bounded flip-width as well. However, the
connections to degree-boundedness were proven even earlier for clique-width
[69] and twin-width [15]. It is also not hard to show that many other classes
of bounded width are degree-bounded, including classes of bounded tree-
independence number [32], mim-width [76], and induced matching treewidth [89,
135].

These connections to width parameters actualy all suggest a more general
trend. Let us say that a class of graphs $\mathcal{F}$ is weakly sparse if
there exists an integer $t$ such that no graph in $\mathcal{F}$ has a subgraph
isomorphic to $K_{t,t}$. This definition was introduced by Nešetřil, Ossona de
Mendez, Rabinovich, and Siebertz [102] to help capture a common trend in
structural graph theory. Namely, that properties of graph classes often come
in pairs, with one property $P_{sparse}$ that is suitable in the sparse
setting, and one property $P_{dense}$ which, informally, extends $P_{sparse}$
to the dense setting. (We think of a graph as being sparse if it has few edges
and dense if it has many edges, informally.) These properties should agree on
every weakly sparse graph class, that is, a class of graphs $\mathcal{F}$
should have property $P_{sparse}$ if and only if $\mathcal{F}$ has property
$P_{dense}$ and $\mathcal{F}$ is weakly sparse.

The following theorem combines some well-known examples of this trend. The
first three bullet points are equivalently stated as [102, Theorem 2.10], the
fourth is from [61], the fifth is stated as [130, Theorem 6.3], and the sixth
as [102, Corollary 2.3]. The final bullet point follows just from the
definitions. The first three bullet points all correspond to width parameters
which are closely related. While it may seem that there are an unbounded
number of width parameters that one could consider, there is a real theory of
width parameters which shows that (many, but not all) well-studied width
parameters are instantiations of one abstract idea. This idea is discussed in
[43], for instance. We also refer the reader to a paper of Gajarský,
Pilipczuk, and Toruńczyk [62] for an explanation of how the following theorem
is connected to transductions in the first-order logic of graphs.

######  Theorem 5.8.

The following statements hold for any graph class $\mathcal{F}$.

  * •

$\mathcal{F}$ has bounded treedepth if and only if $\mathcal{F}$ has bounded
shrubdepth and is weakly sparse.

  * •

$\mathcal{F}$ has bounded pathwidth if and only if $\mathcal{F}$ has bounded
linear rank-width and is weakly sparse.

  * •

$\mathcal{F}$ has bounded treewidth if and only if $\mathcal{F}$ has bounded
rank-width and is weakly sparse.

  * •

$\mathcal{F}$ has bounded maximum degree if and only if $\mathcal{F}$ has
structurally bounded maximum degree and is weakly sparse.

  * •

$\mathcal{F}$ has bounded expansion if and only if $\mathcal{F}$ has bounded
flip-width and is weakly sparse.

  * •

$\mathcal{F}$ is nowhere dense if and only if $\mathcal{F}$ is monadically
dependent and is weakly sparse.

  * •

$\mathcal{F}$ has bounded minimum degree if and only if $\mathcal{F}$ is
degree-bounded and is weakly sparse.

We note that the third bullet point originates with Gurski and Wanke [69], and
that the third and fourth bullet points are proven using a theorem of Dvořák
[45] as the main ingredient.

The point here is that, in well-structured graph classes, forbidding a
biclique as a subgraph is often enough to force a lot of structure (much more
than just bounding the minimum degree). For instance, forbidding all induced
subdivisions of a fixed graph $H$ not only makes the class degree-bounded as
stated in Theorem 3.12, but it also makes every weakly sparse subclass have
bounded expansion; this is the theorem of Dvořák [45]. If $H$ is a path, then
the weakly sparse subclasses even have bounded treedepth [11]. Similarly,
Weißauer [134] showed that if $H$ is a cycle, then the weakly sparse
subclasses have bounded treewidth. Finally, the theorems about separators in
Section 5.3 are yet another example of this trend.

## Acknowledgments

We are grateful to Bryce Frederickson for pointing out the result of Golumbic
and Goss [68, Theorem 4] in connection with degree-perfect graphs.

## References

  * [1] H. Adler and . Adler, _Interpreting nowhere dense graph classes as a classical notion of model theory_ , European J. Combin. 36 (2014), 322–330.
  * [2] M. Ajtai, J. Komlós, and E. Szemerédi, _A note on Ramsey numbers_ , J. Combin. Theory Ser. A 29 (1980), no. 3, 354–360.
  * [3] S. Albrechtsen, T. Huynh, R. W. Jacobs, P. Knappe, and P. Wollan, _A Menger-type theorem for two induced paths_ , arXiv (2024), 2305.04721.
  * [4] E. M. Andreev, _Convex polyhedra of finite volume in Lobačevskiĭ space_ , Mat. Sb. (N.S.) 83(125) (1970), 256–260.
  * [5] M. Axenovich, J. Rollin, and T. Ueckerdt, _Chromatic number of ordered graphs with forbidden ordered subgraphs_ , Combinatorica 38 (2018), no. 5, 1021–1043.
  * [6] A. Basit, A. Chernikov, S. Starchenko, T. Tao, and C.-M. Tran, _Zarankiewicz’s problem for semilinear hypergraphs_ , Forum Math. Sigma 9 (2021), Paper No. e59, 23.
  * [7] I. Benjamini, M. Fraczyk, and G. Kun, _Expander spanning subgraphs with large girth_ , Israel J. Math. 251 (2022), no. 1, 155–171.
  * [8] C. Berge, _Färbung von graphen, deren sämtliche bzw. deren ungerade kreise starr sind_ , Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114.
  * [9] T. Bohman and P. Keevash, _Dynamic concentration of the triangle-free process_ , Random Structures Algorithms 58 (2021), no. 2, 221–293.
  * [10] M. Bonamy, N. Bousquet, L. Esperet, C. Groenland, C.-H. Liu, F. Pirot, and A. Scott, _Asymptotic dimension of minor-closed families and Assouad–Nagata dimension of surfaces_ , J. Eur. Math. Soc. (2023), published online first.
  * [11] M. Bonamy, N. Bousquet, M. Pilipczuk, P. Rzażewski, S. Thomassé, and B. Walczak, _Degeneracy of $P_{t}$-free and $C_{\geqslant t}$-free graphs with no large complete bipartite subgraphs_, J. Combin. Theory Ser. B 152 (2022), 353–378.
  * [12] M. Bonamy and M. Pilipczuk, _Graphs of bounded cliquewidth are polynomially $\chi$-bounded_, Advances in Combinatorics (2020).
  * [13] É. Bonnet, D. Chakraborty, E. J. Kim, N. Köhler, R. Lopes, and S. Thomassé, _Twin-width VIII: delineation and win-wins_ , 17th International Symposium on Parameterized and Exact Computation, LIPIcs. Leibniz Int. Proc. Inform., vol. 249, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022, pp. Paper No. 9, 18.
  * [14] É. Bonnet, C. Geniet, E. J. Kim, S. Thomassé, and R. Watrigant, _Twin-width III: max independent set, min dominating set, and coloring_ , 48th International Colloquium on Automata, Languages, and Programming, LIPIcs. Leibniz Int. Proc. Inform., vol. 198, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021, pp. Art. No. 35, 20.
  * [15] É. Bonnet, C. Geniet, E. J. Kim, S. Thomassé, and R. Watrigant, _Twin-width II: small classes_ , Comb. Theory 2 (2022), no. 2, Paper No. 10, 42.
  * [16] A. Bouchet, _Circle graph obstructions_ , J. Combin. Theory Ser. B 60 (1994), no. 1, 107–144.
  * [17] R. Bourneuf, M. Bucić, L. Cook, and J. Davies, _On polynomial degree-boundedness_ , arXiv (2023), 2311.03341v2.
  * [18] R. Bourneuf and S. Thomassé’, _Bounded twin-width graphs are polynomially $\chi$-bounded_, arXiv (2023), 2303.11231.
  * [19] M. Briański, J. Davies, and B. Walczak, _Separating polynomial $\chi$-boundedness from $\chi$-boundedness_, Combinatorica (2023), https://doi.org/10.1007/s00493–023–00054–3.
  * [20] G. R. Brightwell and E. R. Scheinerman, _Representations of planar graphs_ , SIAM J. Discrete Math. 6 (1993), no. 2, 214–229.
  * [21] M. Bucić’, T. Nguyen, A. Scott, and P. Seymour, _Induced subgraph density. I. a loglog step towards Erdös-Hajnal_ , arXiv (2023), 2301.10147.
  * [22] J. Burling, _On coloring problems of families of polytopes_ , PhD thesis, University of Colorado (1965).
  * [23] A. Carbonero, P. Hompe, B. Moore, and S. Spirkl, _A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number_ , J. Combin. Theory Ser. B 158 (2023), 63–69.
  * [24] J. Chalopin, L. Esperet, Z. Li, and P. Ossona de Mendez, _Restricted frame graphs and a conjecture of Scott_ , Electron. J. Combin. 23 (2016), no. 1, Paper 1.30, 21.
  * [25] M. Chudnovsky, _The Erdös–Hajnal Conjecture—A survey_ , J. Graph Theory 75 (2014), no. 2, 178–190.
  * [26] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, _The strong perfect graph theorem_ , Ann. of Math. (2) 164 (2006), no. 1, 51–229.
  * [27] M. Chudnovsky, A. Scott, and P. Seymour, _Induced subgraphs of graphs with large chromatic number. III. Long holes_ , Combinatorica 37 (2017), no. 6, 1057–1072.
  * [28] M. Chudnovsky, A. Scott, and P. Seymour, _Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings_ , J. Combin. Theory Ser. B 150 (2021), 195–243.
  * [29] M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl, _Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes_ , J. Combin. Theory Ser. B 140 (2020), 84–97.
  * [30] H. Cohn, _A conceptual breakthrough in sphere packing_ , Notices Amer. Math. Soc. 64 (2017), no. 2, 102–115.
  * [31] G Cornuéjols, _Combinatorial optimization_ , ch. 3. Perfect Graphs and Matrices, pp. 21–30, SIAM, CBMS-NSF Regional Conference Series in Applied Mathematics, 2001.
  * [32] C. Dallard, M. Milanič, and K. Štorgel, _Treewidth versus clique number. II. Tree-independence number_ , J. Combin. Theory Ser. B 164 (2024), 404–442.
  * [33] E. Davies and F. Illingworth, _The $\chi$-Ramsey problem for triangle-free graphs_, SIAM J. Discrete Math. 36 (2022), no. 2, 1124–1134.
  * [34] J. Davies, _Improved bounds for colouring circle graphs_ , Proc. Amer. Math. Soc. 150 (2022), no. 12, 5121–5135.
  * [35] J. Davies, _Vertex-minor-closed classes are $\chi$-bounded_, Combinatorica 42 (2022), 1049–1079.
  * [36] J. Davies, T. Krawczyk, R. McCarty, and B. Walczak, _Colouring polygon visibility graphs and their generalizations_ , 37th International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform., vol. 189, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021, pp. Art. No. 29, 16.
  * [37] J. Davies, T. Krawczyk, R. McCarty, and B. Walczak, _Colouring polygon visibility graphs and their generalizations_ , 37th International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform., vol. 189, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021, pp. Art. No. 29, 16.
  * [38] J. Davies, T. Krawczyk, R. McCarty, and B. Walczak, _Grounded L-graphs are polynomially $\chi$-bounded_, Discrete Comput. Geom. 70 (2023), no. 4, 1523–1550.
  * [39] J. Davies and R. McCarty, _Circle graphs are quadratically $\chi$-bounded_, Bull. Lond. Math. Soc. 53 (2021), no. 3, 673–679.
  * [40] H. de Fraysseix, _Local complementation and interlacement graphs_ , Discrete Math. 33 (1981), no. 1, 29–35.
  * [41] D. Dellamonica, Jr., V. Koubek, D. M. Martin, and V. Rödl, _On a conjecture of Thomassen concerning subgraphs of large girth_ , J. Graph Theory 67 (2011), no. 4, 316–331.
  * [42] D. Dellamonica, Jr. and V. Rödl, _A note on Thomassen’s conjecture_ , J. Combin. Theory Ser. B 101 (2011), no. 6, 509–515.
  * [43] M. DeVos, O. Kwon, and S. Oum, _Branch-depth: generalizing tree-depth of graphs_ , European J. Combin. 90 (2020), 103186, 23.
  * [44] X. Du, A. Girão, Z. Hunter, R. McCarty, and A. Scott, _Induced $C_{4}$-free subgraphs with large average degree_, arXiv (2023), 2307.08361v2.
  * [45] Z. Dvořák, _Induced subdivisions and bounded expansion_ , European J. Combin. 69 (2018), 143–148.
  * [46] Z. Dvořák and D. Král’, _Classes of graphs with small rank decompositions are $\chi$-bounded_, European Journal of Combinatorics 33 (2012), no. 4, 679–683.
  * [47] Z. Dvořák, R. McCarty, and S. Norin, _Sublinear separators in intersection graphs of convex shapes_ , SIAM J. Discrete Math. 35 (2021), no. 2, 1149–1164.
  * [48] Z. Dvořák and S. Norin, _Strongly sublinear separators and polynomial expansion_ , SIAM J. Discrete Math. 30 (2016), no. 2, 1095–1101.
  * [49] P. Erdős, _Graph theory and probability_ , Canadian J. Math. 11 (1959), 34–38.
  * [50] P. Erdős and A. Hajnal, _Ramsey-type theorems_ , vol. 25, 1989, Combinatorics and complexity (Chicago, IL, 1987), pp. 37–52.
  * [51] L. Esperet, _Graph colorings, flows and perfect matchings_ , Habilitation thesis, Université Grenoble Alpe (2017), 24.
  * [52] L. Esperet, R. J. Kang, and S. Thomassé, _Separation choosability and dense bipartite induced subgraphs_ , Combin. Probab. Comput. 28 (2019), no. 5, 720–732.
  * [53] G. Fiz Pontiveros, S. Griffiths, and R. Morris, _The triangle-free process and the Ramsey number $R(3,k)$_, Mem. Amer. Math. Soc. 263 (2020), no. 1274, v+125.
  * [54] J. Fox and J. Pach, _A separator theorem for string graphs and its applications_ , Combinatorics, Probability and Computing 19 (2010), no. 3, 371–390.
  * [55] J. Fox and J. Pach, _String graphs and incomparability graphs_ , Adv. Math. 230 (2012), no. 3, 1381–1401.
  * [56] J. Fox and J. Pach, _Applications of a new separator theorem for string graphs_ , Combin. Probab. Comput. 23 (2014), no. 1, 66–74.
  * [57] J. Fox, J. Pach, A. Sheffer, A. Suk, and J. Zahl, _A semi-algebraic version of Zarankiewicz’s problem_ , J. Eur. Math. Soc. (JEMS) 19 (2017), no. 6, 1785–1810.
  * [58] J. Fox, J. Pach, and A. Suk, _Quasiplanar graphs, string graphs, and the Erdős-Gallai problem_ , Graph drawing and network visualization, Lecture Notes in Comput. Sci., vol. 13764, Springer, Cham, [2023] ©2023, pp. 219–231.
  * [59] N. Frankl and A. Kupavskii, _On the Erdős-Purdy problem and the Zarankiewitz problem for semialgebraic graphs_ , arXiv (2021), 2112.10245.
  * [60] Z. Füredi, _On finite set-systems whose every intersection is a kernel of a star_ , Discrete Math. 47 (1983), no. 1, 129–132.
  * [61] J. Gajarský, P. Hliněný, J. Obdržálek, D. Lokshtanov, and M. S. Ramanujan, _A new perspective on FO model checking of dense graph classes_ , ACM Trans. Comput. Log. 21 (2020), no. 4, Art. 28, 23\.
  * [62] J. Gajarský, M. Pilipczuk, and S. Toruńczyk, _Stable graphs of bounded twin-width_ , Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science, ACM, New York, [2022] ©2022, pp. [Article 39], 12.
  * [63] J. Geelen, O. Kwon, R. McCarty, and P. Wollan, _The grid theorem for vertex-minors_ , J. Combin. Theory Ser. B 158 (2023), 93–116.
  * [64] J. Geelen and S. Oum, _Circle graph obstructions under pivoting_ , J. Graph Theory 61 (2009), no. 1, 1–11.
  * [65] A. Georgakopoulos and P. Papasoglu, _Graph minors and metric spaces_ , arXiv (2023), 2305.07456.
  * [66] A. Girão, F. Illingworth, E. Powierski, M. Savery, A. Scott, Y. Tamitegama, and J. Tan, _Induced Subgraphs of Induced Subgraphs of Large Chromatic Number_ , Combinatorica 44 (2024), no. 1, 37–62.
  * [67] A. Girão and Z. Hunter, _Induced subdivisions in $K_{s,s}$-free graphs with polynomial average degree_, arXiv (2024), 2310.18452v3.
  * [68] M. C. Golumbic and C. F. Goss, _Perfect elimination and chordal bipartite graphs_ , J. Graph Theory 2 (1978), no. 2, 155–163.
  * [69] F. Gurski and E. Wanke, _The tree-width of clique-width bounded graphs without $K_{n,n}$_, Graph-theoretic concepts in computer science (Konstanz, 2000), Lecture Notes in Comput. Sci., vol. 1928, Springer, Berlin, 2000, pp. 196–205.
  * [70] A. Gyárfás, _On Ramsey covering-numbers_ , Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vols. I, II, III, Colloq. Math. Soc. János Bolyai, vol. Vol. 10, North-Holland, Amsterdam-London, 1975, pp. 801–816.
  * [71] A. Gyárfás, _On the chromatic number of multiple interval graphs and overlap graphs_ , Discrete Math. 55 (1985), no. 2, 161–166.
  * [72] A. Gyárfás, _Problems from the world surrounding perfect graphs_ , Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), vol. 19, 1987, pp. 413–441.
  * [73] A. Gyárfás, E. Szemerédi, and Zs. Tuza, _Induced subtrees in graphs of large chromatic number_ , Discrete Math. 30 (1980), no. 3, 235–244.
  * [74] S. Har-Peled and K. Quanrud, _Approximation algorithms for polynomial-expansion and low-density graphs_ , SIAM Journal on Computing 46 (2017), no. 6, 1712–1744.
  * [75] Z. Hunter, A. Milojević, B. Sudakov, and I. Tomon, _Kővári-Sós-Turán theorem for hereditary families_ , arXiv (2024), 2401.10853v1.
  * [76] L. Jaffke, O. Kwon, and J. A. Telle, _Mim-Width I. Induced path problems_ , Discrete Appl. Math. 278 (2020), 153–168.
  * [77] O. Janzer and C. Pohoata, _On the Zarankiewicz problem for graphs with bounded VC-dimension_ , arXiv (2021), 2009.00130v2.
  * [78] O. Janzer and B. Sudakov, _Resolution of the Erdős-Sauer problem on regular subgraphs_ , Forum Math. Pi 11 (2023), Paper No. e19, 13.
  * [79] T. Kővári, V. T. Sós, and P. Turán, _On a problem of K. Zarankiewicz_ , Colloq. Math. 3 (1954), 50–57.
  * [80] H. A. Kierstead and S. G. Penrice, _Radius two trees specify $\chi$-bounded classes_, J. Graph Theory 18 (1994), no. 2, 119–129.
  * [81] P. Koebe, _Kontaktprobleme der konformen abbildung_ , Ber. Verh. Sächs. Akad. Leipzig 88, 1936.
  * [82] T. Korhonen and D. Lokshtanov, _Induced-minor-free graphs: Separator theorem, subexponential algorithms, and improved hardness of recognition_ , pp. 5249–5275.
  * [83] A. Kostochka and J. Kratochvíl, _Covering and coloring polygon-circle graphs_ , Discrete Math. 163 (1997), no. 1-3, 299–305.
  * [84] Jan Kratochvíl, _String graphs. II. Recognizing string graphs is NP-hard_ , J. Combin. Theory Ser. B 52 (1991), no. 1, 67–78.
  * [85] D. Kühn and D. Osthus, _Every graph of sufficiently large average degree contains a $C_{4}$-free subgraph of large average degree_, Combinatorica 24 (2004), no. 1, 155–162.
  * [86] D. Kühn and D. Osthus, _Induced subdivisions in $K_{s,s}$-free graphs of large average degree_, Combinatorica 24 (2004), no. 2, 287–304.
  * [87] M. Kwan, S. Letzter, B. Sudakov, and T. Tran, _Dense induced bipartite subgraphs in triangle-free graphs_ , Combinatorica 40 (2020), no. 2, 283–305.
  * [88] J. R. Lee, _Separators in region intersection graphs_ , 8th Innovations in Theoretical Computer Science Conference, LIPIcs. Leibniz Int. Proc. Inform., vol. 67, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, pp. Art. No. 1, 8.
  * [89] P. T. Lima, M. Milanič, P. Muršič, K. Okrasa, P. Rzażewski, and K. Štorgel, _Tree decompositions meet induced matchings: beyond Max Weight Independent Set_ , arXiv (2024), 2402.15834.
  * [90] R. J. Lipton and R. E. Tarjan, _A separator theorem for planar graphs_ , SIAM J. Appl. Math. 36 (1979), no. 2, 177–189.
  * [91] X. Liu, J. Schroeder, Z. Wang, and X. Yu, _Polynomial $\chi$-binding functions for $t$-broom-free graphs_, J. Combin. Theory Ser. B 162 (2023), 118–133.
  * [92] P.-S. Loh, M. Tait, C. Timmons, and R. M. Zhou, _Induced Turán numbers_ , Combin. Probab. Comput. 27 (2018), no. 2, 274–288.
  * [93] L. Lovász, _Normal hypergraphs and the weak perfect graph conjecture_ , Topics on perfect graphs, North-Holland Math. Stud., vol. 88, North-Holland, Amsterdam, 1984, pp. 29–42.
  * [94] J. Matoušek, _Near-optimal separators in string graphs_ , Combin. Probab. Comput. 23 (2014), no. 1, 135–139.
  * [95] J. Matoušek, _String graphs and separators_ , Geometry, structure and randomness in combinatorics, CRM Series, vol. 18, Ed. Norm., Pisa, 2015, pp. 61–97.
  * [96] R. McCarty, _Dense induced subgraphs of dense bipartite graphs_ , SIAM J. Discrete Math. 35 (2021), no. 2, 661–667.
  * [97] R. McCarty, _Local structure for vertex-minors_ , PhD thesis, University of Waterloo (2021).
  * [98] S. McGuinness, _On bounding the chromatic number of L-graphs_ , Discrete Math. 154 (1996), no. 1-3, 179–187.
  * [99] S. McGuinness, _Colouring arcwise connected sets in the plane. I_ , Graphs Combin. 16 (2000), no. 4, 429–439.
  * [100] G. L. Miller, S.H. Teng, W. Thurston, and S. A. Vavasis, _Separators for sphere-packings and nearest neighbor graphs_ , J. ACM 44 (1997), no. 1, 1–29.
  * [101] R. Montgomery, A. Pokrovskiy, and B. Sudakov, _$C_{4}$ -free subgraphs with large average degree_, Israel J. Math. 246 (2021), no. 1, 55–71.
  * [102] J. Nešetřil, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz, _Classes of graphs with low complexity: The case of classes with bounded linear rankwidth_ , European J. Combin. 91 (2021), 103223, Colorings and structural graph theory in context (a tribute to Xuding Zhu).
  * [103] T. Nguyen, A. Scott, and P. Seymour, _Induced subgraph density. VII. the five-vertex path_ , arXiv (2023), 2312.15333.
  * [104] T. Nguyen, A. Scott, and P. Seymour, _A counterexample to the coarse Menger conjecture_ , arXiv (2024), 2401.06685.
  * [105] T. Nguyen, A. Scott, and P. Seymour, _Induced subgraph density. VI. Bounded VC-dimension_ , arXiv (2024), 2312.15572v2.
  * [106] S. Oum and P. Seymour, _Approximating clique-width and branch-width_ , J. Combin. Theory Ser. B 96 (2006), no. 4, 514–528.
  * [107] A. Pawlik, J. Kozik, T. Krawczyk, M. Lasoń’, P. Micek, W. T. Trotter, and B. Walczak, _Triangle-free intersection graphs of line segments with large chromatic number_ , J. Combin. Theory Ser. B 105 (2014), 6–10.
  * [108] M. Pilipczuk and M. Sokołowski, _Graphs of bounded twin-width are quasi-polynomially $\chi$-bounded_, J. Combin. Theory Ser. B 161 (2023), 382–406.
  * [109] L. Pyber, V. Rödl, and E. Szemerédi, _Dense graphs without $3$-regular subgraphs_, J. Combin. Theory Ser. B 63 (1995), no. 1, 41–54.
  * [110] N. Robertson and P. D. Seymour, _Graph minors. XIII. The disjoint paths problem_ , J. Combin. Theory Ser. B 63 (1995), no. 1, 65–110.
  * [111] N. Robertson and P. D. Seymour, _Graph minors. XX. Wagner’s conjecture_ , J. Combin. Theory Ser. B 92 (2004), no. 2, 325–357.
  * [112] V. Rödl, _On the chromatic number of subgraphs of a given graph_ , Proc. Amer. Math. Soc. 64 (1977), no. 2, 370–371.
  * [113] N. Sauer, _On the density of families of sets_ , J. Combinatorial Theory Ser. A 13 (1972), 145–147.
  * [114] A. Scott, _Induced trees in graphs of large chromatic number_ , J. Graph Theory 24 (1997), no. 4, 297–311.
  * [115] A. Scott and P. Seymour, _Induced subgraphs of graphs with large chromatic number. VI. Banana trees_ , J. Combin. Theory Ser. B 145 (2020), 487–510.
  * [116] A. Scott and P. Seymour, _A survey of $\chi$-boundedness_, J. Graph Theory 95 (2020), no. 3, 473–504.
  * [117] A. Scott, P. Seymour, and S. Spirkl, _Polynomial bounds for chromatic number. III. Excluding a double star_ , J. Graph Theory 101 (2022), no. 2, 323–340.
  * [118] A. Scott, P. Seymour, and S. Spirkl, _Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree_ , J. Graph Theory 102 (2023), no. 3, 458–471.
  * [119] A. Scott, P. Seymour, and S. Spirkl, _Polynomial bounds for chromatic number. IV: A near-polynomial bound for excluding the five-vertex path_ , Combinatorica 43 (2023), no. 5, 845–852.
  * [120] P. D. Seymour and R. Thomas, _Graph searching and a min-max theorem for tree-width_ , J. Combin. Theory Ser. B 58 (1993), no. 1, 22–33.
  * [121] S. Shelah, _A combinatorial problem; stability and order for models and theories in infinitary languages_ , Pacific J. Math. 41 (1972), 247–261.
  * [122] W.D. Smith and N.C. Wormald, _Geometric separator theorems and applications_ , Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), 1998, pp. 232–243.
  * [123] J. Solymosi and T. Tao, _An incidence theorem in higher dimensions_ , Discrete Comput. Geom. 48 (2012), no. 2, 255–280.
  * [124] A. Suk and I. Tomon, _Hasse diagrams with large chromatic number_ , Bull. Lond. Math. Soc. 53 (2021), no. 3, 747–758.
  * [125] D. P. Sumner, _Subtrees of a graph and the chromatic number_ , The theory and applications of graphs (Kalamazoo, Mich., 1980), Wiley, New York, 1981, pp. 557–576.
  * [126] E. Szemerédi and W. T. Trotter, _Extremal problems in discrete geometry_ , Combinatorica 3 (1983), no. 3-4, 381–392.
  * [127] C. Thomassen, _Girth in graphs_ , J. Combin. Theory Ser. B 35 (1983), no. 2, 129–141.
  * [128] W. P. Thurston, _The geometry and topology of three-manifolds. Vol. IV_ , American Mathematical Society, Providence, RI, [2022] ©2022, Edited and with a preface by Steven P. Kerckhoff and a chapter by J. W. Milnor.
  * [129] I. Tomon and D. Zakharov, _Turán-type results for intersection graphs of boxes_ , Combin. Probab. Comput. 30 (2021), no. 6, 982–987.
  * [130] S. Toruńczyk, _Flip-width: Cops and robber on dense graphs_ , 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) (Los Alamitos, CA, USA), IEEE Computer Society, nov 2023, pp. 663–700.
  * [131] V. G. Vizing, _Critical graphs with given chromatic class_ , Diskret. Analiz (1965), no. 5, 9–17.
  * [132] B. Walczak, _Coloring triangle-free L-graphs with $O(\log\log n)$ colors_, European J. Combin. 117 (2024), Paper no. 103831.
  * [133] M. N. Walsh, _The polynomial method over varieties_ , Invent. Math. 222 (2020), no. 2, 469–512.
  * [134] D. Weißauer, _In absence of long chordless cycles, large tree-width becomes a local phenomenon_ , J. Combin. Theory Ser. B 139 (2019), 342–352.
  * [135] N. Yolov, _Minor-matching hypertree width_ , Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2018, pp. 219–233.