
A class of graphs is $\chi$bounded if there is a function $f$ such that
$\chi(G)\le f(\omega(G))$ for every induced subgraph $G$ of every graph in the
class, where $\chi,\omega$ denote the chromatic number and clique number of $G$
respectively. In 1987, Gy\'arf\'as conjectured that for every $c$, if
$\mathcal{C}$ is a class of graphs such that $\chi(G)\le \omega(G)+c$ for every
induced subgraph $G$ of every graph in the class, then the class of complements
of members of $\mathcal{C}$ is $\chi$bounded. We prove this conjecture.
Indeed, more generally, a class of graphs is $\chi$bounded if it has the
property that no graph in the class has $c+1$ odd holes, pairwise disjoint and
with no edges between them. The main tool is a lemma that if $C$ is a shortest
odd hole in a graph, and $X$ is the set of vertices with at least five
neighbours in $V(C)$, then there is a threevertex set that dominates $X$.

A vertex u of a graph tdominates a vertex v if there are at most t vertices
different from u,v that are adjacent to v and not to u; and a graph is
tdominating if for every pair of distinct vertices, one of them tdominates
the other. Our main result says that if a graph is tdominating, then it is
close (in an appropriate sense) to being 0dominating. We also show that an
analogous statement for digraphs is false; and discuss some connections with
the ErdosHajnal conjecture.

Given $k$ pairs of vertices $(s_i,t_i)\;(1\le i\le k)$ of a digraph $G$, how
can we test whether there exist vertexdisjoint directed paths from $s_i$ to
$t_i$ for $1\le i\le k$? This is NPcomplete in general digraphs, even for $k =
2$, but in an earlier paper we proved that for all fixed $k$, there is a
polynomialtime algorithm to solve the problem if $G$ is a tournament (or more
generally, a semicomplete digraph). Here we prove that for all fixed $k$ there
is a polynomialtime algorithm to solve the problem when $V(G)$ is partitioned
into a bounded number of sets each inducing a semicomplete digraph (and we are
given the partition).

For graphs $G$ and $H$, an $H$colouring of $G$ is a map
$\psi:V(G)\rightarrow V(H)$ such that $ij\in E(G)\Rightarrow\psi(i)\psi(j)\in
E(H)$. The number of $H$colourings of $G$ is denoted by $\hom(G,H)$.
We prove the following: for all graphs $H$ and $\delta\geq3$, there is a
constant $\kappa(\delta,H)$ such that, if $n\geq\kappa(\delta,H)$, the graph
$K_{\delta,n\delta}$ maximises the number of $H$colourings among all
connected graphs with $n$ vertices and minimum degree $\delta$. This answers a
question of Engbers.
We also disprove a conjecture of Engbers on the graph $G$ that maximises the
number of $H$colourings when the assumption of the connectivity of $G$ is
dropped.
Finally, let $H$ be a graph with maximum degree $k$. We show that, if $H$
does not contain the complete looped graph on $k$ vertices or $K_{k,k}$ as a
component and $\delta\geq\delta_0(H)$, then the following holds: for $n$
sufficiently large, the graph $K_{\delta,n\delta}$ maximises the number of
$H$colourings among all graphs on $n$ vertices with minimum degree $\delta$.
This partially answers another question of Engbers.

A large body of research in graph theory concerns the induced subgraphs of
graphs with large chromatic number, and especially which induced cycles must
occur. In this paper, we unify and substantially extend results from a number
of previous papers, showing that, for every positive integer k, every graph
with large chromatic number contains either a large complete subgraph or
induced cycles of all lengths modulo k. As an application, we prove two
conjectures of Kalai and Meshulam from the 1990's connecting the chromatic
number of a graph with the homology of its independence complex.

A graph $H$ is pervasive (in some class of graphs) if for all $t\ge 1$, every
graph in the class of bounded clique number and sufficiently large chromatic
number has an induced subgraph that is a subdivision of $H$ in which every edge
of $H$ is replaced by a path of at least $t$ edges. It is known that every
forest and cycle is pervasive in the class of all graphs.
Which other graphs are pervasive? It is known that every such graph is a
forest of chandeliers (every block is obtained from a tree by adding a vertex
adjacent to its leaves, and there are rules about how blocks fit together). It
is not known whether every forest of chandeliers is pervasive in the class of
all graphs.
Say a class of graphs is $r$controlled if for every graph in the class, its
chromatic number is at most some function (determined by the class) of the
largest chromatic number of an $r$ball in the graph. In this paper we prove
that for every $r\ge 2$, and for every $r$controlled class, every forest of
chandeliers is pervasive in this class. In a later paper, two of us build on
the results here to prove that a large class of forests of chandeliers is
pervasive in the class of all graphs.
Our results turn out particularly nicely when applied to string graphs. A
string graph is the intersection graph of a set of curves in the plane. It is
known that there are string graphs with clique number two and chromatic number
arbitrarily large. We prove that the class of string graphs is $2$controlled,
and consequently every forest of chandeliers is pervasive in this class; in
fact, we show that every string graph with bounded clique number and
sufficiently large chromatic number contains each fixed chandelier as an
induced subgraph (not just as a subdivision).

We prove a conjecture of Andras Gyarfas, that for all k,t, every graph with
clique number at most k and sufficiently large chromatic number has an odd hole
of length at least t.

The "clustered chromatic number" of a class of graphs is the minimum integer
$k$ such that for some integer $c$ every graph in the class is $k$colourable
with monochromatic components of size at most $c$. We prove that for every
graph $H$, the clustered chromatic number of the class of $H$minorfree graphs
is tied to the treedepth of $H$. In particular, if $H$ is connected with
treedepth $t$ then every $H$minorfree graph is $(2^{t+1}4)$colourable with
monochromatic components of size at most $c(H)$. This provides the first
evidence for a conjecture of Ossona de Mendez, Oum and Wood (2016) about
defective colouring of $H$minorfree graphs. If $t=3$ then we prove that 4
colours suffice, which is best possible. We also determine those minorclosed
graph classes with clustered chromatic number 2. Finally, we develop a
conjecture for the clustered chromatic number of an arbitrary minorclosed
class.

The classical stability theorem of Erd\H{o}s and Simonovits states that, for
any fixed graph with chromatic number $k+1 \ge 3$, the following holds: every
$n$vertex graph that is $H$free and has within $o(n^2)$ of the maximal
possible number of edges can be made into the $k$partite Tur\'{a}n graph by
adding and deleting $o(n^2)$ edges. In this paper, we prove sharper
quantitative results for graphs $H$ with a critical edge, both for the
Erd\H{o}sSimonovits Theorem (distance to the Tur\'{a}n graph) and for the
closely related question of how close an $H$free graph is to being
$k$partite. In many cases, these results are optimal to within a constant
factor.

Let $u_k(G,p)$ be the maximum over all $k$vertex graphs $F$ of by how much
the number of induced copies of $F$ in $G$ differs from its expectation in the
binomial random graph with the same number of vertices as $G$ and with edge
probability $p$. This may be viewed as a measure of how close $G$ is to being
$p$quasirandom. For a positive integer $n$ and $0<p<1$, let $D(n,p)$ be the
distance from $p\binom{n}{2}$ to the nearest integer. Our main result is that,
for fixed $k\ge 4$ and for $n$ large, the minimum of $u_k(G,p)$ over $n$vertex
graphs has order of magnitude $\Theta\big(\max\{D(n,p), p(1p)\} n^{k2}\big)$
provided that $p(1p)n^{1/2} \to \infty$.

A cat and mouse play a pursuit and evasion game on a connected graph $G$ with
$n$ vertices. The mouse moves to vertices $m_1,m_2,\dots$ of $G$ where $m_i$ is
in the closed neighbourhood of $m_{i1}$ for $i\geq2$. The cat tests vertices
$c_1,c_2,\dots$ of $G$ without restriction and is told whether the distance
between $c_i$ and $m_i$ is at most the distance between $c_{i1}$ and
$m_{i1}$. The mouse knows the cat's strategy, but the cat does not know the
mouse's strategy. We will show that the cat can determine the position of the
mouse up to distance $O(\sqrt{n})$ within finite time and that this bound is
tight up to a constant factor. This disproves a conjecture of Dayanikli and
Rautenbach.

A graph is called $P_t$free if it does not contain the path on $t$ vertices
as an induced subgraph. Let $H$ be a multigraph with the property that any two
distinct vertices share at most one common neighbour. We show that the
generating function for (list) graph homomorphisms from $G$ to $H$ can be
calculated in subexponential time $2^{O\left(\sqrt{tn\log(n)}\right)}$ for
$n=V(G)$ in the class of $P_t$free graphs $G$. As a corollary, we show that
the number of 3colourings of a $P_t$free graph $G$ can be found in
subexponential time. On the other hand, no subexponential time algorithm exists
for 4colourability of $P_t$free graphs assuming the Exponential Time
Hypothesis. Along the way, we prove that $P_t$free graphs have pathwidth that
is linear in their maximum degree.

Reed and Seymour [1998] asked whether every graph has a partition into
induced connected nonempty bipartite subgraphs such that the quotient graph is
chordal. If true, this would have significant ramifications for Hadwiger's
Conjecture. We prove that the answer is `no'. In fact, we show that the answer
is still `no' for several relaxations of the question.

We prove that the dimension of every poset whose comparability graph has
maximum degree $\Delta$ is at most $\Delta\log^{1+o(1)} \Delta$. This result
improves on a 30year old bound of F\"uredi and Kahn, and is within a
$\log^{o(1)}\Delta$ factor of optimal. We prove this result via the notion of
boxicity. The \emph{boxicity} of a graph $G$ is the minimum integer $d$ such
that $G$ is the intersection graph of $d$dimensional axisaligned boxes. We
prove that every graph with maximum degree $\Delta$ has boxicity at most
$\Delta\log^{1+o(1)} \Delta$, which is also within a $\log^{o(1)}\Delta$ factor
of optimal. We also show that the maximum boxicity of graphs with Euler genus
$g$ is $\Theta(\sqrt{g \log g})$, which solves an open problem of Esperet and
Joret and is tight up to a $O(1)$ factor.

We prove that for every graph H there exists c>0 such that, for every graph
G, if G has no clique or stable set of size G^c, then either G or its
complement contains an induced subdivision of H. This follows from a stronger
result for sparse graphs which says, roughly, that every sparse graph contains
either an induced subdivision of H or two linearsized sets of vertices with no
edges between them. These results are related to the ErdosHajnal conjecture.

We study a higherdimensional 'ballsintobins' problem. An infinite sequence
of i.i.d. random vectors is revealed to us one vector at a time, and we are
required to partition these vectors into a fixed number of bins in such a way
as to keep the sums of the vectors in the different bins close together; how
close can we keep these sums almost surely? This question, our primary focus in
this paper, is closely related to the classical problem of partitioning a
sequence of vectors into balanced subsequences, in addition to having
applications to some problems in computer science.

The ErdosHajnal conjecture says that for every graph $H$ there exists $c>0$
such that $\max(\alpha(G),\omega(G))\ge n^c$ for every $H$free graph $G$ with
$n$ vertices, and this is still open when $H=C_5$. Until now the best bound
known on $\max(\alpha(G),\omega(G))$ for $C_5$free graphs was the general
bound of Erdos and Hajnal, that for all $H$, $\max(\alpha(G),\omega(G))\ge
2^{\Omega(\sqrt{\log n })}$ if $G$ is $H$free. We improve this when $H=C_5$ to
$\max(\alpha(G),\omega(G))\ge 2^{\Omega(\sqrt{\log n \log \log n})}.$

A hole in a graph is an induced subgraph which is a cycle of length at least
four. We prove that for every positive integer k, every trianglefree graph
with sufficiently large chromatic number contains holes of k consecutive
lengths.

Let $H$ be an induced subgraph of the torus $C_k^m$. We show that when $k \ge
3$ is even and $V(H)$ divides some power of $k$, then for sufficiently large
$n$ the torus $C_k^n$ has a perfect vertexpacking with induced copies of $H$.
On the other hand, disproving a conjecture of Gruslys, we show that when $k$ is
odd and not a prime power, then there exists $H$ such that $V(H)$ divides
some power of $k$, but there is no $n$ such that $C_k^n$ has a perfect
vertexpacking with copies of $H$. We also disprove a conjecture of Gruslys,
Leader and Tan by exhibiting a subgraph $H$ of the $k$dimensional hypercube
$Q_k$, such that there is no $n$ for which $Q_n$ has a perfect edgepacking
with copies of $H$.

Let 0<p<1 be fixed. Shamir and Spencer proved in the 1980s that the chromatic
number of a random graph in G(n,p) is concentrated in an interval of length
about n^{1/2}. In this explanatory note, we give a proof of a result due due
Noga Alon, showing that the chromatic number is concentrated in an interval of
length about n^{1/2}/log n.

We give a construction of rpartite runiform intersecting hypergraphs with
cover number at least r4 for all but finitely many r. This answers a question
of AbuKhazneh, Barat, Pokrovskiy and Szabo, and shows that a longstanding
unsolved conjecture due to Ryser is close to being best possible for every
value of r.

We consider 'supersaturation' problems in partially ordered sets (posets) of
the following form. Given a finite poset $P$ and an integer $m$ greater than
the cardinality of the largest antichain in $P$, what is the minimum number of
comparable pairs in a subset of $P$ of cardinality $m$? We provide a framework
for obtaining lower bounds on this quantity based on counting comparable pairs
relative to a random chain and apply this framework to obtain supersaturation
results for three classical posets: the boolean lattice, the collection of
subspaces of $\mathbb{F}_q^n$ ordered by set inclusion and the set of divisors
of the square of a squarefree integer under the 'divides' relation. The bound
that we obtain for the boolean lattice can be viewed as an approximate version
of a known theorem of Kleitman.
In addition, we apply our supersaturation results to obtain (a) upper bounds
on the number of antichains in these posets and (b) asymptotic bounds on the
cardinality of the largest antichain in $p$random subsets of these posets
which hold with high probability (for $p$ in a certain range). The proofs of
these results rely on a 'containertype' lemma for posets which generalises a
result of Balogh, Mycroft and Treglown. We also state a number of open problems
regarding supersaturation in posets and counting antichains.

We prove that for all nonnegative integers k,s there exists c with the
following property. Let G be a graph with clique number at most k and chromatic
number more than c. Then for every vertexcolouring (not necessarily optimal)
of G, some induced subgraph of G is an svertex path, and all its vertices have
different colours. This extends a recent result of Gyarfas and Sarkozy, who
proved the same (when k=2) for graphs G with girth at least five.

We determine the maximum number of induced cycles that can be contained in a
graph on $n\ge n_0$ vertices, and show that there is a unique graph that
achieves this maximum. This answers a question of Tuza. We also determine the
maximum number of odd or even cycles that can be contained in a graph on $n\ge
n_0$ vertices and characterise the extremal graphs. This resolves a conjecture
of Chv\'atal and Tuza from 1988.

We investigate which graphs H have the property that in every graph with
bounded clique number and sufficiently large chromatic number, some induced
subgraph is isomorphic to a subdivision of H. In an earlier paper, one of us
proved that every tree has this property; and in another earlier paper with M.
Chudnovsky, we proved that every cycle has this property. Here we give a common
generalization. Say a banana is the union of a set of paths all with the same
ends but otherwise disjoint. We prove that if H is obtained from a tree by
replacing each edge by a banana then H has the property mentioned. We also find
some other multigraphs with the same property.