Vida Dujmović, Pat Morin, Sergey Norin et al.
We show that every $n$-vertex planar graph is 3-colourable with monochromatic components of size $O(n^{4/9})$. The best previous bound was $O(n^{1/2})$ due to Linial, Matoušek, Sheffet and Tardos [Combin. Probab. Comput., 2008].
Vida Dujmović, Robert Hickingbotham, Jędrzej Hodor et al.
We prove that for every planar graph $X$ of treedepth $h$, there exists a positive integer $c$ such that for every $X$-minor-free graph $G$, there exists a graph $H$ of treewidth at most $f(h)$ such that $G$ is isomorphic to a subgraph of $H\boxtimes K_c$. This is a qualitative strengthening of the Grid-Minor Theorem of Robertson and Seymour (JCTB 1986), and treedepth is the optimal parameter in such a result. As an example application, we use this result to improve the upper bound for weak coloring numbers of graphs excluding a fixed graph as a minor.
David R. Wood
Tree-decompositions of graphs are of fundamental importance in structural and algorithmic graph theory. The main property of tree-decompositions is the width (the maximum size of a bag $-1$). We show that every graph has a tree-decomposition with near-optimal width, plus several additional properties of interest. In particular every graph $G$ with treewidth at most $k$ has a tree-decomposition with width at most $72k+1$, where each vertex $v$ appears in at most $\text{deg}_G(v)+1$ bags, the number of bags is at most $\max\{\frac{|V(G)|}{2k},1\}$, and the tree indexing the decomposition has maximum degree at most 12. This improves exponential bounds to linear in a result of Ding and Oporowski [1995], and establishes a conjecture of theirs in a strong sense.