Abstract. We give a short proof that for every apex-forest [Formula: see text] on at least two vertices, graphs excluding [Formula: see text] as a minor have layered pathwidth at most [Formula: see text]. This improves upon a result by Dujmović, Eppstein, Joret, Morin, and Wood (SIDMA, 2020). Our main tool is a structural result about graphs excluding a forest as a rooted minor, which is of independent interest. We develop similar tools for treedepth and treewidth. We discuss implications for Erdős-Pósa properties of rooted models of minors in graphs.

We study the growth rate of weak coloring numbers of graphs excluding a fixed graph as a minor. Van den Heuvel et al. (European J. of Combinatorics, 2017) showed that for a fixed graph X, the maximum r-th weak coloring number of X-minor-free graphs is polynomial in r. We determine this polynomial up to a factor of O (r log r ). Moreover, we tie the exponent of the polynomial to a structural property of X, namely, 2-treedepth. As a result, for a fixed graph X and an X-minor-free graph G, we show that wcolr(G ) = O (rtd(X )-1 log r ), which improves on the bound wcolr(G ) = O (rg(td(X ))) given by Dujmović et al. (SODA, 2024), where g is an exponential function. In the case of planar graphs of bounded treewidth, we show that the maximum r-th weak coloring number is in O (r2 log r ), which is best possible.

Abstract Given a positive integer d, the class d-DIR is defined as all those intersection graphs formed from a finite collection of line segments in $${\mathbb R}^2$$ R 2 having at most d slopes. Since each slope induces an interval graph, it easily follows for every G in d-DIR with clique number at most $$\omega $$ ω that the chromatic number $$\chi (G)$$ χ ( G ) of G is at most $$d\omega $$ d ω . We show for every even value of $$\omega $$ ω how to construct a graph in d-DIR that meets this bound exactly. This partially confirms a conjecture of Bhattacharya, Dvořák and Noorizadeh. Furthermore, we show that the $$\chi $$ χ -binding function of d-DIR is $$\omega \mapsto d\omega $$ ω ↦ d ω for $$\omega $$ ω even and $$\omega \mapsto d(\omega -1)+1$$ ω ↦ d ( ω - 1 ) + 1 for $$\omega $$ ω odd. This extends an earlier result by Kostochka and Nešetřil, which treated the special case $$d=2$$ d = 2 .

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 ⊠ Kc. 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 given graph as a minor.