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 show that every n-vertex planar graph is contained in the graph obtained from a fan by blowing up each vertex by a complete graph of order ). Equivalently, every n-vertex planar graph G has a set X of ) vertices such that G — X has bandwidth ). This result holds in the more general setting of graphs contained in the strong product of a bounded treewidth graph and a path, which includes bounded genus graphs, graphs excluding a fixed apex graph as a minor, and k-planar graphs for fixed k. These results are obtained using two ingredients. The first is a new local sparsification lemma, which shows that every n-vertex planar graph G has a set of O ((n log n )/D ) vertices whose removal results in a graph with local density at most D. The second is a generalization of a method of Feige and Rao, that relates bandwidth and local density using volume-preserving Euclidean embeddings.

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.

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.

We prove that every poset with bounded cliquewidth and with sufficiently large dimension contains the standard example of dimension k as a subposet. This applies in particular to posets whose cover graphs have bounded treewidth, as the cliquewidth of a poset is bounded in terms of the treewidth of the cover graph. For the latter posets, we prove a stronger statement: every such poset with sufficiently large dimension contains the Kelly example of dimension k as a subposet. Using this result, we obtain a full characterization of the minor-closed graph classes C such that posets with cover graphs in C have bounded dimension: they are exactly the classes excluding the cover graph of some Kelly example. Finally, we consider a variant of poset dimension called Boolean dimension, and we prove that posets with bounded cliquewidth have bounded Boolean dimension.

Abstract. Alon, Seymour, and Thomas [ J. Amer. Math. Soc., 3 (1990), pp. 801–808] proved that every [Formula: see text]-vertex graph excluding [Formula: see text] as a minor has treewidth less than [Formula: see text]. Illingworth, Scott, and Wood [ Product Structure of Graphs with an Excluded Minor, preprint, arXiv:2104.06627 , 2022] recently refined this result by showing that every such graph is a subgraph of some graph with treewidth [Formula: see text], where each vertex is blown up by a complete graph of order [Formula: see text]. Solving an open problem of Illingworth, Scott, and Wood [2022], we prove that the treewidth bound can be reduced to 4 while keeping blowups of order [Formula: see text]. As an extension of the Lipton–Tarjan theorem, in the case of planar graphs, we show that the treewidth can be further reduced to 2, which is best possible. We generalize this result for [Formula: see text]-minor-free graphs, with blowups of order [Formula: see text]. This setting includes graphs embeddable on any fixed surface.

We study reconfiguration of independent sets in interval graphs under the token sliding rule. We show that if two independent sets of size k are reconfigurable in an n-vertex interval graph, then there is a reconfiguration sequence of length 𝒪(k⋅ n²). We also provide a construction in which the shortest reconfiguration sequence is of length Ω(k²⋅ n). As a counterpart to these results, we also establish that Independent Set Reconfiguration is PSPACE-hard on incomparability graphs, of which interval graphs are a special case.

We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an n -vertex planar graph G is assigned a (1 + o(1)) log 2 n -bit label and the labels of two vertices u and v are sufficient to determine if uv is an edge of G . This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every positive integer n , there exists a graph U n with n 1+o(1) vertices such that every n -vertex planar graph is an induced subgraph of U n . These results generalize to a number of other graph classes, including bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k -planar graphs.

We prove that for every nowhere dense class of graphs $\mathcal{C}$, positive integer $d$, and $\varepsilon>0$, the following holds: in every $n$-vertex graph $G$ from $\mathcal{C}$ one can find two disjoint vertex subsets $A,B\subseteq V(G)$ such that $|A|\geq (1/2-\varepsilon)\cdot n$ and $|B|=\Omega(n^{1-\varepsilon})$; and either ${dist}(a,b)\leq d$ for all $a\in A$ and $b\in B$, or ${dist}(a,b)>d$ for all $a\in A$ and $b\in B$. We also show some stronger variants of this statement, including a generalization to the setting of first-order interpretations of nowhere dense graph classes.

We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an n-vertex planar graph G is assigned a (1+o(1))log2n-bit label and the labels of two vertices u and v are sufficient to determine if uv is an edge of G. This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every positive integer n, there exists a graph Un with n1+o(1)vertices such that every n-vertex planar graph is an induced subgraph of Un. These results generalize to a number of other graph classes, including bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k-planar graphs.

A vertex coloring φ of a graph G is p-centered if for every connected subgraph H of G either φ uses more than p colors on H or there is a color that appears exactly once on H Centered colorings form one of the families of parameters that allow to capture notions of sparsity of graphs: A class of graphs has bounded expansion if and only if there is a function f such that for every p ≥ 1, every graph in the class admits a p-centered coloring using at most f(p) colors. In this paper, we give upper bounds for the maximum number of colors needed in a p-centered coloring of graphs from several widely studied graph classes. We show that: (1) planar graphs admit p-centered colorings with (p3 log p) colors where the previous bound was (p19); (2) bounded degree graphs admit p-centered colorings with (p) colors while it was conjectured that they may require exponential number of colors in p; (3) graphs avoiding a fixed graph as a topological minor admit p-centered colorings with a polynomial in p number of colors. All these upper bounds imply polynomial algorithms for computing the colorings. Prior to this work there were no non-trivial lower bounds known. We show that: (4) there are graphs of treewidth t that require colors in any p-centered coloring and this bound matches the upper bound; (5) there are planar graphs that require Ω(p2 log p) colors in any p-centered coloring. We also give asymptotically tight bounds for outerplanar graphs and planar graphs of treewidth 3. We prove our results with various proof techniques. The upper bound for planar graphs involves an application of a recent structure theorem while the upper bound for bounded degree graphs comes from the entropy compression method. We lift the result for bounded degree graphs to graphs avoiding a fixed topological minor using the Grohe-Marx structure theorem.

We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath et al. [66] from 1992. The key to the proof is a new structural tool called layered partitions , and the result that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number. Layered partitions have strong connections to other topics, including the following two examples. First, they can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes. Second, we give a simple proof of the result by DeVos et al. [31] that graphs in a proper minor-closed class have low treewidth colourings.

We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath, Leighton and Rosenberg from 1992. The key to the proof is a new structural tool called layered partitions, and the result that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number. Layered partitions can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes.

The existence of an on-line competitive algorithm for coloring bipartite graphs is a tantalizing open problem. So far there are only partial positive results for bipartite graphs with certain small forbidden graphs as induced subgraphs. We propose an on-line competitive coloring algorithm for $$P_9$$ -free bipartite graphs.

We prove that every planar poset $P$ of height $h$ has dimension at most $192h+96$. This improves on previous exponential bounds and is best possible up to a constant factor. We complement this result with a construction of planar posets of height $h$ and dimension at least $(4/3)h-2$.

We prove that posets of bounded height whose cover graphs belong to a fixed class with bounded expansion have bounded dimension. Bounded expansion, introduced by Nešetřil and Ossona de Mendez as a model for sparsity in graphs, is a property that is naturally satisfied by a wide range of graph classes, from graph structure theory (graphs excluding a minor or a topological minor) to graph drawing (e.g. graphs with constant book thickness). Therefore, our theorem generalizes a number of results including the most recent one for posets of bounded height with cover graphs excluding a fixed graph as a topological minor (Walczak, SODA 2015). We also show that the result is in a sense best possible, as it does not extend to nowhere dense classes; in fact, it already fails for cover graphs with locally bounded treewidth.

We study on-line colorings of certain graphs given as intersection graphs of objects "between two lines", i.e., there is a pair of horizontal lines such that each object of the representation is a connected set contained in the strip between the lines and touches both. Some of the graph classes admitting such a representation are permutation graphs (segments), interval graphs (axis-aligned rectangles), trapezoid graphs (trapezoids) and cocomparability graphs (simple curves). We present an on-line algorithm coloring graphs given by convex sets between two lines that uses O(w^3) colors on graphs with maximum clique size w. In contrast intersection graphs of segments attached to a single line may force any on-line coloring algorithm to use an arbitrary number of colors even when w=2. The left-of relation makes the complement of intersection graphs of objects between two lines into a poset. As an aside we discuss the relation of the class C of posets obtained from convex sets between two lines with some other classes of posets: all 2-dimensional posets and all posets of height 2 are in C but there is a 3-dimensional poset of height 3 that does not belong to C. We also show that the on-line coloring problem for curves between two lines is as hard as the on-line chain partition problem for arbitrary posets.

We give new positive results on the long-standing open problem of geometric covering decomposition for homothetic polygons. In particular, we prove that for any positive integer k, every finite set of points in ℝ3 can be colored with k colors so that every translate of the negative octant containing at least k6 points contains at least one of each color. The best previously known bound was doubly exponential in k. This yields, among other corollaries, the first polynomial bound for the decomposability of multiple coverings by homothetic triangles. We also investigate related decomposition problems involving intervals appearing on a line. We prove that no algorithm can dynamically maintain a decomposition of a multiple covering by intervals under insertion of new intervals, even in a semi-online model, in which some coloring decisions can be delayed. This implies that a wide range of sweeping plane algorithms cannot guarantee any bound even for special cases of the octant problem.

A family of sets in the plane is simple if the intersection of any subfamily is arc-connected, and it is pierced by a line $$L$$ if the intersection of any member with $$L$$ is a nonempty segment. It is proved that the intersection graphs of simple families of compact arc-connected sets in the plane pierced by a common line have chromatic number bounded by a function of their clique number.

We give new positive results on the long-standing open problem of geometric covering decomposition for homothetic polygons. In particular, we prove that for any positive integer $k$, every finite set of points in $\mathbb{R}^3$ can be colored with $k$ colors so that every translate of the negative octant containing at least $k^6$ points contains at least one of each color. The best previously known bound was doubly exponential in $k$. This yields, among other corollaries, the first polynomial bound for the decomposability of multiple coverings by homothetic triangles. We also investigate related decomposition problems involving intervals appearing on a line. We prove that no algorithm can dynamically maintain a decomposition of a multiple covering by intervals under insertion of new intervals, even in a semionline model, in which some coloring decisions can be delayed. This implies that a wide range of sweeping plane algorithms cannot guarantee any bound even for special cases of the octant problem.

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set $$X$$ in $$\mathbb{R }^2$$ that is not an axis-aligned rectangle and for any positive integer $$k$$ produces a family $$\mathcal{F }$$ of sets, each obtained by an independent horizontal and vertical scaling and translation of $$X$$ , such that no three sets in $$\mathcal{F }$$ pairwise intersect and $$\chi (\mathcal{F })>k$$ . This provides a negative answer to a question of Gyárfás and Lehel for L-shapes. With extra conditions we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries or equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.

A nonrepetitive coloring of a path is a coloring of its vertices such that the sequence of colors along the path does not contain two identical, consecutive blocks. The remarkable construction of Thue asserts that three colors are enough to color nonrepetitively paths of any length. A nonrepetitive coloring of a graph is a coloring of its vertices such that all simple paths are nonrepetitively colored. Assume that each vertex $v$ of a graph $G$ has assigned a set (list) of colors $L_v$. A coloring is chosen from $\{{L_v}_{v\in V(G)}\}$ if the color of each $v$ belongs to $L_v$. The Thue choice number of $G$, denoted by $\pi_l(G)$, is the minimum $k$ such that for any list assignment $\{{L_v}\}$ of $G$ with each $|{L_v}|\geqslant k$ there is a nonrepetitive coloring of $G$ chosen from $\{{L_v}\}$. Alon et al. proved in 2002 that $\pi_l(G)=O(\Delta^2)$ for every graph $G$ with maximum degree at most $\Delta$. We propose an almost linear bound in $\Delta$ for trees, namely, for any $\varepsilon>0$ there is a constant $c$ such that $\pi_l(T)\leqslant c\Delta^{1+\varepsilon}$ for every tree $T$ with maximum degree $\Delta$. The only lower bound for trees is given by a recent result of Fiorenzi et al. that for any $\Delta$ there is a tree $T$ such that $\pi_l(T)=\Omega(\frac{\log\Delta}{\log \log \Delta})$. We also show that if one allows repetitions in a coloring but still forbids three identical consecutive blocks of colors on any simple path, then a constant size of the lists allows one to color any tree.