Clustered Colouring of Odd-$H$-Minor-Free Graphs

We consider simple, finite, undirected graphs $G$ with vertex-set ${V(G)}$ and edge-set ${E(G)}$. See [3] for graph-theoretic definitions not given here. Let ${\mathbb{N}\coloneqq\{1,2,\dots\}}$ and ${\mathbb{N}_{\_}0\coloneqq\{0,1,\dots\}}$. For $n\in\mathbb{N}$, let $[n]\coloneq\{1,\dots,n\}$.

A colouring of a graph $G$ is a function that assigns one colour to each vertex of $G$. For an integer $k\geqslant 1$, a $k$-colouring is a colouring using at most $k$ colours. A colouring of a graph is proper if each pair of adjacent vertices receives distinct colours. The chromatic number $\chi(G)$ of a graph $G$ is the minimum integer $k$ such that $G$ has a proper $k$-colouring. A graph $H$ is a minor of a graph $G$ if $H$ is isomorphic to a graph that can be obtained from a subgraph of G by contracting edges. A graph $G$ is $H$-minor-free if $H$ is not a minor of $G$. Let $\mathcal{G}_{\_}H$ denote the class of $H$-minor-free graphs. Hadwiger [8] famously conjectured that $\chi(G)\leqslant h-1$ for every $K_{\_}h$-minor-free graph $G$. This is one of the most important open problems in graph theory. The best known upper bound on the chromatic number of $K_{\_}h$-minor-free graphs is $O(h\log\log h)$ due to Delcourt and Postle [1] (see [15, 27, 21] for previous bounds). It is open whether every $K_{\_}h$-minor-free graph is properly $O(h)$-colourable. See [24] for a survey on this conjecture.

We consider the intersection of both a relaxation and a strengthening of Hadwiger’s conjecture. First, the relaxation. For $k\in\mathbb{N}_{\_}0$, a colouring has clustering $k$ if each monochromatic component has at most $k$ vertices. The clustered chromatic number $\chi_{\_}{\star}(\mathcal{G})$ of a graph class $\mathcal{G}$ is the minimum $c\in\mathbb{N}_{\_}0$ for which there exists $k\in\mathbb{N}_{\_}0$ such that every graph $G\in\mathcal{G}$ can be $c$-coloured with clustering $k$. Similarly, the defective chromatic number $\chi_{\_}{\Delta}(\mathcal{G})$ of a graph class $\mathcal{G}$ is the minimum $c\in\mathbb{N}_{\_}0$ for which there exists $d\in\mathbb{N}_{\_}0$ such that every graph $G\in\mathcal{G}$ can be $c$-coloured with each monochromatic component having maximum degree at most $d$. See [30] for a survey on clustered and defective colouring.

Motivated by Hadwiger’s conjecture, Edwards et al. [6] proved a defective variant: $\chi_{\_}{\Delta}(\mathcal{G}_{\_}{K_{\_}h})=h-1$ for all $h\in\mathbb{N}$. They also introduced the Clustered Hadwiger Conjecture: for all $h\in\mathbb{N}$,

$$\chi_{\_}{\star}(\mathcal{G}_{\_}{K_{\_}h})=h-1.$$

Kawarabayashi and Mohar [14] had previously proved the first $O(h)$ upper bound on $\chi_{\_}{\star}(\mathcal{G}_{\_}{K_{\_}h})$. The constant in the $O(h)$ term was successively improved [14, 28, 6, 20, 17, 29, 18, 19], before a proof of the Clustered Hadwiger Conjecture was first announced to appear in a future paper by Dvořák and Norin [5]. Their full proof has not yet been made public. Dujmović et al. [4] recently proved the conjecture.

Now for the strengthening of Hadwiger’s conjecture. Let $G$ and $H$ be graphs. An $H$-model in $G$ is a collection $\mathcal{H}=(T_{\_}x:x\in V(H))$ of pairwise vertex-disjoint subtrees of $G$ such that for each $xy\in E(H)$, there is an edge of $G$ joining $T_{\_}x$ and $T_{\_}y$. We denote by $G\langle\mathcal{H}\rangle$ the subgraph of $G$ that is the union $\bigcup(T_{\_}x\colon x\in V(H))$ together with the edges in $G$ joining $T_{\_}x$ and $T_{\_}y$ for each $xy\in E(H)$. Clearly $H$ is a minor of $G$ if and only if there exists an $H$-model in $G$. We call $\mathcal{H}$ odd if there is a $2$-colouring $c$ of $G\langle\mathcal{H}\rangle$ such that:

• •

  for each $x\in V(H)$, $T_{\_}x$ is properly $2$-coloured by $c$; and

• •

  for each $xy\in E(H)$, there is a monochromatic edge in $G\langle\mathcal{H}\rangle$ joining $T_{\_}x$ and $T_{\_}y$.

We say $c$ witnesses that $\mathcal{H}$ is odd. If there is an odd $H$-model in $G$, then we say that $H$ is an odd-minor of $G$. A graph $G$ is $H$-odd-minor-free if $H$ is not an odd-minor of $G$. Let $\mathcal{G}_{\_}H^{\text{odd}}$ denote the class of $H$-odd-minor-free graphs.

As a qualitative strengthening of Hadwiger’s conjecture, Gerards and Seymour [10, pp. 115] introduced the Odd Hadwiger Conjecture: $\chi(G)\leqslant h-1$ for every $K_{\_}h$-odd-minor-free graph $G$. Note that in the case when $h=3$, excluding $K_{\_}3$ as an odd-minor is equivalent to excluding an odd cycle as a subgraph, so the class of $K_{\_}3$-odd-minor-free graphs is exactly the class of all bipartite graphs. Recently, Steiner [25] showed that the Odd Hadwiger Conjecture is asymptotically equivalent to Hadwiger’s conjecture, in the sense that if every $K_{\_}t$-minor-free graph is properly $f(t)$-colourable, then every $K_{\_}t$-odd-minor-free graph is properly $2\,f(t)$-colourable.

We are interested in understanding the clustered chromatic number of graph classes defined by a forbidden odd-minor $H$. How does the structure of $H$ relate to the clustered chromatic number of $\mathcal{G}_{\_}H^{\text{odd}}$? Kawarabayashi [13] first proved $\chi_{\_}{\star}(\mathcal{G}_{\_}{K_{\_}h}^{\text{odd}})\in O(h)$. The constant factor term in the $O(h)$ was improved in [12, 18], culminating in a result of Steiner [26] who showed that $\chi_{\_}{\star}(\mathcal{G}_{\_}{K_{\_}h}^{\text{odd}})\leqslant 2h-2$ using chordal partitions. So $\chi_{\_}{\star}(\mathcal{G}_{\_}H^{\text{odd}})\leqslant 2|V(H)|-2$ for every graph $H$. We show that the clustered chromatic number of $\mathcal{G}_{\_}H^{\text{odd}}$ is tied to the connected tree-depth of $H$, which we now define.

The vertex-height of a rooted tree $T$ is the maximum number of vertices on a path from a root to a leaf in $T$. For two vertices $u$, $v$ in a rooted tree $T$, we say that $u$ is a descendant of $v$ in $T$ if $v$ lies on the path from the root to $u$ in $T$. The closure of $T$ is the graph with vertex set $V(T)$ where $uv\in E(T)$ if $u$ is a descendant of $v$ or vice versa. The connected tree-depth $\operatorname{\overline{td}}(G)$ of a graph $G$ is the minimum vertex-height of a rooted tree $T$ with $V(T)=V(G)$ such that $G$ is a subgraph of the closure of $T$^***A forest is rooted if each component has a root vertex (which defines the ancestor relation). The closure of a rooted forest $F$ is the disjoint union of the closure of each rooted component of $F$. The tree-depth $\operatorname{td}(G)$ of a graph $G$ is the minimum vertex-height of a rooted forest $F$ with $V(F)=V(G)$ such that $G$ is a subgraph of the closure of $F$. If $G$ is connected, then $\operatorname{td}(G)=\operatorname{\overline{td}}(G)$. In fact, $\operatorname{td}(G)=\operatorname{\overline{td}}(G)$ unless $G$ has two connected components $G_{\_}1$ and $G_{\_}2$ with $\operatorname{td}(G_{\_}1)=\operatorname{td}(G_{\_}2)=\operatorname{td}(G)$, in which case $\operatorname{\overline{td}}(G)=\operatorname{td}(G)+1$..

Ossona de Mendez et al. [23] showed that $\operatorname{\overline{td}}(H)$ is a lower bound for the defective chromatic number of $\mathcal{G}_{\_}H$. In particular, for every graph $H$,

$$\operatorname{\overline{td}}(H)-1\leqslant\chi_{\_}{\Delta}(\mathcal{G}_{\_}H).$$

Ossona de Mendez et al. [23] conjectured that this inequality holds with equality. A partial answer to this conjecture was given by Norin et al. [22], who showed that the defective chromatic number of $\mathcal{G}_{\_}H$, the clustered chromatic number of $\mathcal{G}_{\_}H$, and the connected tree-depth of $H$ are tied. In particular,

$$\operatorname{\overline{td}}(H)-1\leqslant\chi_{\_}{\Delta}(\mathcal{G}_{\_}H)\leqslant\chi_{\_}{\star}(\mathcal{G}_{\_}H)\leqslant 2^{\operatorname{\overline{td}}(H)+1}-4.$$

(1)

Norin et al. [22] also gave examples of graphs $H$ such that $\chi_{\_}{\star}(\mathcal{G}_{\_}H)\geqslant 2\operatorname{\overline{td}}(H)-2$, and conjectured that $\chi_{\_}{\star}(\mathcal{G}_{\_}H)\leqslant 2\operatorname{\overline{td}}(H)-2$ for every graph $H$. Recently, Liu [16] proved the above conjecture of Ossona de Mendez et al. [23] which, together with a result in Liu and Oum [17], implies that for every graph $H$,

$$\operatorname{\overline{td}}(H)-1=\chi_{\_}{\Delta}(\mathcal{G}_{\_}H)\leqslant\chi_{\_}{\star}(\mathcal{G}_{\_}H)\leqslant 3\chi_{\_}{\Delta}(\mathcal{G}_{\_}H)\leqslant 3\operatorname{\overline{td}}(H)-3.$$

Now consider the defective and clustered chromatic numbers of $\mathcal{G}_{\_}H^{\text{odd}}$. We prove the following analogue of the above result of Norin et al. [22] for odd-minors.

Liu and Wood [18] proved that for every graph $H$ and for all integers $s,t\in\mathbb{N}$, every $H$-odd-minor-free $K_{\_}{s,t}$-subgraph-free graph is $(2s+1)$-colourable with clustering at most some function $f(H,s,t)$. With $s=1$ this says that for every graph $H$ and integer $t$, every $H$-odd-minor-free graph with maximum degree less than $t$ is 3-colourable with clustering at most some function $f(H,t)$. This implies that $\chi_{\_}{\star}(\mathcal{G}_{\_}H^{\text{odd}})\leqslant 3\,\chi_{\_}{\Delta}(\mathcal{G}_{\_}H^{\text{odd}})$.

We now work towards proving Theorem 1. Our proof uses the same strategy that Norin et al. [22] used to prove (1) with some modifications in the odd-minor-free setting.

We need the following definition. A tree-decomposition of a graph $G$ is a collection ${\mathcal{W}=(W_{\_}x\colon x\in V(T))}$ of subsets of ${V(G)}$ indexed by the nodes of a tree $T$ such that (a) for every edge ${vw\in E(G)}$, there exists a node ${x\in V(T)}$ with ${v,w\in W_{\_}x}$; and (b) for every vertex ${v\in V(G)}$, the set ${\{x\in V(T)\colon v\in W_{\_}x\}}$ induces a non-empty (connected) subtree of $T$. The width of $\mathcal{W}$ is ${\max\{\lvert W_{\_}x\rvert\colon x\in V(T)\}-1}$. The treewidth $\operatorname{tw}(G)$ of a graph $G$ is the minimum width of a tree-decomposition of $G$. Treewidth is the standard measure of how similar a graph is to a tree. Indeed, a connected graph has treewidth at most 1 if and only if it is a tree.

The following result due to Demaine et al. [2] allows us to work in the bounded treewidth setting.

The following Erdős-Pósa type result is folklore (see [9, Lemma 9] which implies this).

For $h,d\in\mathbb{N}$, let $U_{\_}{h,d}$ be the closure of the complete $d$-ary tree of vertex-height $h$. Observe that $U_{\_}{h,d}$ has connected tree-depth $h$. Moreover, for every graph $H$ of connected tree-depth at most $h$, $H$ is isomorphic to a subgraph of $U_{\_}{h,d}$ for $d=|V(H)|$. So to prove Theorem 1, it suffices to do so for $U_{\_}{h,d}$ for all $h,d\in\mathbb{N}$.

The next definition is critical in allowing us to lift the proof of Norin et al. [22] from the minor-free setting to the odd-minor-free setting. Say an $H$-model $(T_{\_}x:x\in V(H))$ in $G$ is non-trivial if $|V(T_{\_}x)|\geqslant 2$ for each $x\in V(H)$. Non-trivial models have been previously studied, for example, in [7]. The next lemma is the heart of the paper.

We are now ready to prove our main result.