The chromatic number $\chi(G)$ of a graph $G$ is always at least the size of its largest clique (denoted by $\omega(G)$), and there are graphs $G$ with $\omega(G)=2$ and $\chi(G)$ arbitrarily large.
On the other hand, the perfect graph theorem asserts that if neither $G$ nor its complement has an odd hole, then $\chi(G)=\omega(G)$ . (A "hole" is an induced cycle of length at least four, and "odd holes" are holes of odd length.) What happens in between?
With Alex Scott, we recently proved the following, a 1985 conjecture of Gyárfás:

For graphs $G$ with no odd hole, $\chi(G)$ is bounded by a function of $\omega(G)$.

Gyárfás also made the stronger conjecture that for every integer $k$ and for all graphs $G$ with no odd hole of length more than $k$, $\chi(G)$ is bounded by a function of $k$ and $\omega(G)=2$. This is far from settled, and indeed the following much weaker statement is not settled: for every integer $k$, every triangle-free graph with no hole of length at least $k$ has chromatic number bounded by a function of $k$. We give a partial result towards the latter:

For all $k$, every triangle-free graph with no hole of length at least $k$ admits a tree-decomposition into bags with chromatic number bounded by a function of $k$.

Both results have quite pretty proofs, which will more-or-less be given in full.[-]

A central concept in graph theory is the notion of tree decompositions - these are decompositions that allow us to split a graph up into "nice" pieces by "small" cuts. It is possible to solve many algorithmic problems on graphs by decomposing the graph into "nice" pieces, finding a solution in each of the pieces, and then gluing these solutions together to form a solution to the entire graph. Examples of this approach include algorithms for deciding whether a given input graph is planar, the $k$-Disjoint paths algorithm of Robertson and Seymour, as well as many algorithms on graphs of bounded tree-width. In this talk we will look at a way to compare two tree decompositions of the same graph and decide which of the two is "better". It turns out that for every cut size $k$, every graph $G$ has a tree decomposition with (approximately) this cut size, such that this tree-decomposition is "better than" every other tree-decomposition of the same graph with cut size at most $k$. We will discuss some consequences of this result, as well as possible improvements and research directions.[-]