## Quasi-tree-partitions of graphs with an excluded subgraph

Chun-Hung Liu †

David R. Wood ‡

August 5, 2024

## Abstract

This paper studies the structure of graphs with given tree-width and excluding a fixed complete bipartite subgraph, which generalises the bounded degree setting. We give a new structural description of such graphs in terms of so-called quasi-tree-partitions. We demonstrate the utility of this result through applications to (fractional) clustered colouring. Further generalisations of these structural and colouring results are presented.

## 1 Introduction

Treewidth is the standard measure of how similar a graph is to a tree. It is an important parameter in structural graph theory, especially Robertson and Seymour's Graph Minors project, and also in algorithmic graph theory, since many NP-complete problems are solvable in linear time on graphs with bounded tree-width. See [6, 47, 71] for surveys on tree-width.

We now define tree-width. For a tree T , a T -decomposition of a graph G is a collection ( B x ) x ∈ V ( T ) such that:

- · B x ⊆ V ( G ) for each x ∈ V ( T ) ,
- · for every edge vw ∈ E G ( ) , there exists a node x ∈ V ( T ) with { v, w } ⊆ B x , and
- · for every vertex v ∈ V ( G ) , the set { x ∈ V ( T ): v ∈ B x } induces a non-empty (connected) subtree of T .

The width of such a T -decomposition is max {| B x | : x ∈ V ( T ) } -1 . A tree-decomposition is a T -decomposition for some tree T , denoted ( T, ( B x x ) ∈ V ( T ) ) . The tree-width tw( G ) of a graph G is the minimum width of a tree-decomposition of G . Treewidth is a standard measure of how similar a graph is to a tree. Indeed, a connected graph has tree-width at most 1 if and only if it is a tree.

At the heart of this paper is the following question: What is the structure of graphs with tree-width k ? Without some additional assumption, not much more can be said beyond the

† Department of Mathematics, Texas A&amp;M University, USA ( chliu@tamu.edu ). Partially supported by NSF under CAREER award DMS-2144042.

‡ School of Mathematics, Monash University, Melbourne, Australia ( david.wood@monash.edu ). Research supported by the Australian Research Council.

Figure 1: A tree-partition of width 2.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00983v1-figure-45efcb63-108b-44ce-b282-79c944331965.jpg)

definition. But with some additional assumption about an excluded subgraph, much more can be said about the structure of graphs with tree-width k . We need the following definition, illustrated in Figure 1. For a tree T , a T -partition of a graph G is a collection ( B x x ) ∈ V ( T ) such that:

- · ⋃ x ∈ V ( T ) B x = V ( G ) and B x ∩ B y = ∅ for distinct x, y ∈ V ( T ) , · for every edge vw of G , if v ∈ B x and w ∈ B y , then x = y or xy ∈ E T ( ) .

The width of such a T -partition is max {| B x | : x ∈ V ( T ) } . A tree-partition is a T -partition for some tree T , denoted ( T, ( B x ) x ∈ V ( T ) ) . The tree-partition-width tpw( G ) of a graph G is the minimum width of a tree-partition of G . Tree-partitions were independently introduced by Seese [74] and Halin [46], and have since been widely investigated [7-9, 19, 20, 34, 35, 78, 80]. Tree-partition-width has also been called strong tree-width [8, 74]. Tree-partitions are also related to graph product structure theory, since for any tree T , a graph G has a T -partition of width at most k if and only if G is isomorphic to a subgraph of T ⊠ K k ; see [11, 25, 30] for example.

It is easily seen that tw( G ) ⩽ 2tpw( G ) -1 for every graph G [74]. But conversely, treepartition-width cannot be upper bounded by a function of tree-width. For example, the n -vertex fan has tree-width 2 and tree-partition-width Θ( √ n ) , which was implicitly shown by Ding and Oporowski [20, (3.6)]. On the other hand, tree-partition-width is upper bounded by a function of tree-width and maximum degree. In particular, a referee of a paper by Ding and Oporowski [19] showed the following:

Theorem 1 ([19]) . For k, ∆ ∈ N , every graph with tree-width k and maximum degree ∆ has tree-partition-width O k ( ∆) .

This result is incredibly useful, and has found applications in diverse areas including graph drawing [13, 18, 27, 29, 83], graphs of linear growth [12], nonrepetitive graph colouring [3], clustered graph colouring [1, 59], fractional fragility [34], monadic second-order logic [56], network emulations [4, 5, 10, 42], statistical learning theory [84], size Ramsey numbers [23,

50], and the edge-Erdős-Pósa property [14, 43, 70]. The essential reason for the usefulness of Theorem 1 is that in a tree-partition each vertex appears only once, unlike in a treedecomposition.

Note that the dependence on tree-width and maximum degree in Theorem 1 is best possible up to a constant factor. Wood [80] showed that for any k ⩾ 3 and sufficiently large ∆ there is a graph with tree-width k , maximum degree ∆ , and tree-partition-width Ω( ∆) k .

Theorem 1 has been extended in various ways. For example, Distel and Wood [21, 22] showed the same result where the underlying tree has maximum degree O (∆( G )) and at most max { | V ( G ) | 2 k , 1 } vertices.

This paper explores structural descriptions of graphs with tree-width k that satisfy some weaker assumption than bounded degree. A graph G contains a graph H if some subgraph of G is isomorphic to H . On the other hand, G is H -subgraph-free if no subgraph of G is isomorphic to H .

The following definitions are a key aspect of the paper. Consider a tree T rooted at node r ∈ V ( T ) . For each node x ∈ V ( T ) , let

$$T \uparrow x \coloneqq \{ y \in V ( T ) \colon \, \text{dist} _ { T } ( r, y ) < \text{dist} _ { T } ( r, x ) \},$$

where dist T ( r, y ) is the distance in T between r and y , which is the minimum number of edges of a path in T between r and y . As illustrated in Figure 2, for k ∈ N 0 and a rooted tree T , a k -quasiT -partition of a graph G is a pair T = (( B x ) x ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) where:

- · ( B x ) x ∈ V ( T ) is a T -partition of G -⋃ v ∈ V ( G ) E v , and · for each v ∈ V ( G ) , E v is a set of at most k edges in G incident with v , and for each edge vw ∈ E v , if v ∈ B x and w ∈ B y then y ∈ T ↑ x .

The width of T is max {| B x | : x ∈ V ( T ) } . The degree of T is ∆( T ) . A k -quasi-tree-partition is a k -quasiT -partition for some rooted tree T , denoted ( T, ( B x ) x ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) . Note that 0 -quasi-tree-partitions are exactly tree-partitions.

A k -quasiT -partition (( B x x ) ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) of a graph G is clean if for each edge vw ∈ E v , if v ∈ B x and w ∈ B y then y is a non-parent ancestor of x in T . This strengthens the condition that y ∈ T ↑ x .

Our main results apply to graphs satisfying a certain sparsity condition, which we now introduce. Let δ G ( ) and ∆( G ) be the minimum degree and maximum degree of a graph G respectively. The 1-subdivision of a graph H is the graph obtained from H by replacing each edge vw of H by a path vxw internally disjoint from the rest of the graph. Let ρ G ( ) be the maximum of δ H ( ) taken over all graphs H such that the 1-subdivision of H is a subgraph of G .

We prove the following result for graphs of given tree-width that exclude a complete bipartite subgraph, where the 'weight' term is explained in Section 1.1.

Theorem 2. For any s, t, k, ρ ∈ N , every K s,t -subgraph-free graph G with tw( G ) ⩽ k and ρ G ( ) ⩽ ρ has a clean ( s -1) -quasi-tree-partition of width O tρ ( s -1 k ) , degree O tρ ( s -1 ) , and weight O k ( ) .

Figure 2: A k -quasi-tree-partition, where E v = { vx, vy, vz } . Dashed edges are not allowed. Without edge vz , the quasi-tree-partition is clean.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00983v1-figure-22f5326e-c8b5-4bac-8218-9dd2fae4f069.jpg)

The main point of Theorem 2 is that the 'quasiness' of the quasi-tree-partition depends only on s (which we may assume is at most t by symmetry, and is often much less than k ). Moreover, we show that the ' ( s -1) -quasi' term in Theorem 2 is best possible (see Section 4.1).

In (3) below, we show that ρ G ( ) ⩽ tw( G ) . Thus, Theorem 2 implies:

Corollary 3. For any s, t, k ∈ N , every K s,t -subgraph-free graph G with tree-width at most k has a clean ( s -1) -quasi-tree-partition of width O tk ( s ) , degree O tk ( s -1 ) , and weight O k ( ) .

Note that a graph is K 1 ,t -subgraph-free if and only if it has maximum degree less than t , and a 0-quasi-tree-partition is precisely a tree-partition. So the s = 1 case of Corollary 3 implies Theorem 1, as well as matching the known degree bound from [21, 22] (up to a constant factor).

We are mainly interested in graphs of bounded tree-width, but we emphasise that the dependence on k in Theorem 2 is linear (for fixed s, t, ρ ). Thus Theorem 11 gives interesting results even when tree-width is not bounded, such as for planar graphs and more generally for graphs G of Euler genus g . It follows from Euler's formula that G is K 3 2 , g +3 -subgraph-free, and ρ G ( ) ∈ O ( √ g +1) . Results about balanced separators by Gilbert, Hutchinson, and Tarjan [44] imply that tw( G ) ∈ O ( √ ( g +1) | V ( G ) ) | . The next result thus follows directly from Theorem 2.

Corollary 4. For any g ∈ N 0 every graph G with Euler genus g has a clean 2 -quasi-treepartition of width O (( g +1) tw( 2 G )) = O (( g +1) 5 2 / | V ( G ) | 1 2 / ) , degree O (( g +1) ) 2 , and weight O (tw( G )) = O (( g +1) 1 2 / | V ( G ) | 1 2 / ) .

We prove Theorem 2 in Section 3, where we also give more motivating examples for minor-closed and non-minor-closed graph classes.

Corollary 3 has applications to clustered colouring and fractional clustered colouring, which we present in Section 4.

Section 5 presents a number of extensions and generalisations of Theorem 2 and Corollary 3 for (non-clean) quasi-tree-partitions, where we relax the K s,t -subgraph-free assumption as follows. As illustrated in Figure 3, for s, t ∈ N , a graph G is a 1-extension of K s,t if G contains a connected subgraph H such that contracting H into a vertex creates a graph isomorphic to K 1 ,s,t . Note that K s +1 ,t is a minor of any 1-extension of K s,t . A graph G is a skewered K s,t if it can be obtained from K s,t by adding a path disjoint from the s -vertex side and passing through all vertices in the t -vertex side.

Figure 3: (a) 1-extension of K 4 6 , , and (b) skewered K 4 6 , .

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00983v1-figure-89b2f98d-7de8-4047-83b5-eca8674055bf.jpg)

We prove the following extension of Theorem 2 (see Theorem 28 for a more precise statement).

Theorem 5. For any s, a, b, k, ρ ∈ N with a, b ⩾ 2 , every graph G with tw( G ) ⩽ k and ρ G ( ) ⩽ ρ that contains no 1-extension of K s,a and contains no skewered K s,b has a clean ( s -1) -quasi-tree-partition of width O ((( s + ab ab ) + ) k ρ s -1 k ) .

The width in Theorem 5 can be improved by dropping the cleanness of the quasi-tree-partition.

Theorem 6. For any s, a, b, k, ρ ∈ N with a, b ⩾ 2 , every graph G with tw( G ) ⩽ k and ρ G ( ) ⩽ ρ that contains no 1-extension of K s,a and contains no skewered K s,b has an ( s -1) -quasi-tree-partition of width O (( s + ab abρ ) s -1 k ) .

Recall that ρ G ( ) ⩽ tw( G ) by (3). Thus Theorem 6 implies the following extension of Corollary 3 (see Corollary 30 for a more precise statement).

Corollary 7. For any s, a, b, k ∈ N with a, b ⩾ 2 , every graph G of tree-width at most k that contains no 1-extension of K s,a and contains no skewered K s,b has an ( s -1) -quasi-tree-partition of width O (( s + ab abk ) s ) .

This result with s = 1 implies the following qualitative strengthening of the original result for tree-partitions (Theorem 1), since every graph with maximum degree ∆ contains no 1-extension of K 1 ∆+1 , and contains no skewered K 1 ∆+1 ,

Corollary 8. For any a, b, k ∈ N every graph G with tw( G ) ⩽ k that contains no 1-extension of K 1 ,a and no skewered K 1 ,b has tree-partition-width O a b k ( 2 2 ) .

## 1.1 Weight

We now explain the 'weight' term in the above results. Intuitively, the weight of a quasi-treepartition is the 'cost' of converting it into a tree-decomposition without extensively changing the ancestor-descendant relation of the bags. More formally, say T = ( T, ( B x ) x ∈ V ( T ) , ( E v ) v ∈ V ( G ) )

is a clean quasi-tree-partition of a graph G . For each node x ∈ V ( T ) , define the load C x to be the set of vertices w ∈ V ( G ) , such that there exists an edge vw ∈ E v with v ∈ B y and w ∈ B a , where a is a non-parent ancestor of x in T , and y = x or y is a descendent of x in T . The weight of T is max {| C x | : x ∈ V ( T ) } . This property is interesting for the following reason. If r is the root of T , then define ̂ B r := B r . For each non-root node x ∈ V ( T ) with parent y ∈ V ( T ) , define ̂ B x := B x ∪ B y ∪ C x . Then ̂ T := ( T, ( ̂ B x ) x ∈ V ( T ) ) is a tree-decomposition of G , since for each edge vw ∈ E G ( ) with v ∈ B x and w ∈ B y , where y is an ancestor of x or y = x , the vertex w is in ̂ B q for each node q on the xy -path in T . So, if T has width k and weight w , then ̂ T has width at most 2 k + w -1 , and tw( G ) ⩽ 2 k + w -1 . Thus, if T comes from Theorem 2, then ̂ T has width O tρ ( s -1 k ) . Without a bound on the weight of T , this construction of a tree-decomposition might not have bounded width. Indeed, as illustrated in Figure 4, for all n ∈ N there is a graph with tree-width n that has a 1-quasi-tree-partition of width 1 and degree 2. A feature of Theorem 2 is that it produces a quasi-tree-partition that is not far from a tree-decomposition with small width.

Figure 4: Order the vertices of the n × n grid (which has tree-width n ) by following the blue path P . This defines a clean quasiP -partition of width 1. Each vertex v has at most one neighbour that is not a neighbour in P and appears before v in P . Thus this is a clean 1-quasiP -partition.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00983v1-figure-4bbc760c-42d7-4519-9fec-61fe907883de.jpg)

## 2 Preliminaries

In this paper, N := { 1 2 , , . . . } and N 0 := { 0 1 2 , , , . . . } .

We consider simple finite undirected graphs G with vertex-set V ( G ) and edge-set E G ( ) .

A rooted tree is a tree T with a nominated vertex called the root . Consider a tree T rooted at a vertex r . A path P in T is vertical if the vertex in P closest to r is an endpoint of P . Consider a non-root vertex x in T , and let P be the xr -path in T . Every vertex y in P -x is an ancestor of x , and x is a descendent of y . The neighbour y of x on P is the parent of x , and x is a child of y .

A graph class is a collection of graphs closed under isomorphism. A graph class G is proper if some graph is not in G . A graph class G is hereditary if for every graph G , every induced

subgraph of G is in G . A graph class G is monotone if for every graph G ∈ G , every subgraph of G is in G .

A graph H is a minor of a graph G if a graph isomorphic to H can be obtained from G by deleting vertices and edges, and contracting edges. A graph class G is minor-closed if for every graph G ∈ G , every minor of G is in G . For example, for each k ∈ N 0 , the class of graphs with tree-width at most k is minor-closed.

A surface is a compact 2-dimensional manifold. For any fixed surface Σ , the class of graphs embeddable on Σ (without crossings) is minor-closed. A surface with h handles and c cross-caps has Euler genus 2 h + c . The Euler genus of a graph G is the minimum Euler genus of a surface in which G embeds.

Consider a graph G . For each vertex v ∈ V ( G ) , let N G ( v ) be the set of neighbours of v in G . Now consider a set X ⊆ V ( G ) . For s ∈ N , let N ⩾ s G ( X ) be the set of vertices in V ( G ) -X with at least s neighbours in X . Let N G ( X ) := N ⩾ 1 G ( X ) . A common neighbour of X is a vertex v with X ⊆ N G ( v ) ; that is, v ∈ N ⩾ | X | G ( X ) .

Let G be a graph. By considering a leaf bag, it is well-known and easily seen that,

$$\delta ( G ) \leqslant \text{tw} ( G ).$$

For d ∈ N 0 , G is d -degenerate if δ H ( ) ⩽ d for every subgraph H of G . The degeneracy degen( G ) of G is the maximum of δ H ( ) , taken over all subgraphs H of G . It is well-known and easily seen that

$$\chi ( G ) - 1 \leqslant \deg e n ( G ) \leqslant \text{tw} ( G ).$$

Note that degeneracy can be characterised via quasi-tree-partitions.

Proposition 9. For k ∈ N , a graph G is k -degenerate if and only if G has a ( k -1) -quasitree-partition of width 1.

̸

Proof. ( ⇐ =) Assume G has a ( k -1) -quasi-tree-partition ( T, ( B x x ) ∈ V ( T ) ) of width 1. Given any subgraph H of G , let x be a deepest bag of T such that B x ∩ V ( H ) = ∅ , and let v ∈ B x ∩ V ( H ) . Let y be the parent of x in T . By the choice of x , deg G ( v ) ⩽ | E v | + | B y | ⩽ k . Hence G is k -degenerate.

̸

(= ⇒ ) We proceed by induction on | V ( G ) | . The base case is trivial. Let G be a k -degenerate graph. So G has a vertex v of degree at most k . By induction, G -v has a ( k -1) -quasi-treepartition of width 1. Let y be a deepest node in T such that B y ∩ N G ( v ) = ∅ ; if N G ( v ) = ∅ . then let y be the root of T . Add a child node x of y to T . Let B x := { v } . We obtain a ( k -1) -quasi-tree-partition of G of width 1, where E v := { vw ∈ E G ( ) : w ∈ N G ( v ) \ B y } .

Note that Proposition 9 generalises the construction of a quasi-tree-partition of the grid graph illustrated in Figure 4.

Note the following upper bound on ρ G ( ) . Say the 1-subdivision H ′ of a graph H is a subgraph of a graph G . Then δ H ( ) ⩽ tw( H ) by (1), and tw( H ′ ) ⩽ tw( G ) since tree-width is monotone

under taking subgraphs. It is well-known and easily seen that tw( H ) = tw( H ′ ) (for any subdivision H ′ of H ). Combining these facts, δ H ( ) ⩽ tw( H ) = tw( H ′ ) ⩽ tw( G ) . Hence

$$\rho ( G ) \leqslant \text{tw} ( G ).$$

We need the following variation on a result of Ossona de Mendez, Oum, and Wood [69], where K ∗ s,t is the graph obtained from K s,t by adding ( ) s 2 new vertices, each adjacent to a distinct pair of vertices in the colour class of s vertices in K s,t , as illustrated in Figure 5.

## Lemma 10. For any s, t, ρ ∈ N , let

$$\mathbf 0. \ F o r \ a n y \ s, t, \rho \in \mathbb { N }, \ l e t \\ c \coloneqq c ( s, t, \rho ) \coloneqq \begin{cases} t & \text{when $s=1$} \\ 1 + \rho + ( t - 1 ) \binom { \rho } { s - 1 } & \text{when $s\geqslant 2$.} \end{cases} \\ \text{very $K_{s,t}^{*}$-subgraph-free $graph $G$ with $\rho(G)$} \leqslant \rho, \ a n d \ f o r \ a n y \ s e t \ X \subseteq V ( \iota )$$

Then for every K ∗ s,t -subgraph-free graph G with ρ G ( ) ⩽ ρ , and for any set X ⊆ V ( G ) ,

$$| N _ { G } ^ { \geq s } ( X ) | \leqslant ( c - 1 ) | X |.$$

Proof. If s = 1 then every vertex in X has degree at most t -1 , implying | N ⩾ s G ( X ) | ⩽ ( t -1) | X | = ( c -1) | X | . Now assume that s ⩾ 2 . Let H be the bipartite graph with bipartition { N ⩾ s G ( X , ) ( X 2 ) } , where v ∈ N ⩾ s G ( X ) is adjacent in H to { x, y } ∈ ( X 2 ) whenever { x, y } ⊆ N G ( v ) ∩ X . Let M be a maximal matching in H . Let Q be the graph with vertex-set X , where xy ∈ E Q ( ) whenever { v, { x, y }} ∈ M for some vertex v ∈ N ⩾ s G ( X ) . Thus, the 1-subdivision of every subgraph of Q is a subgraph of G . Hence, Q is ρ -degenerate, implying | M | = | E Q ( ) | ⩽ ρ V | ( Q ) | = ρ X | | . Moreover, Q contains at most ( ρ s -1 ) | X | cliques of size exactly s [68, 79]. Exactly | M | vertices in N ⩾ s G ( X ) are incident with an edge in M . For each vertex v ∈ N ⩾ s G ( X ) not incident with an edge in M , by maximality, N G ( v ) ∩ X is a clique in Q of size at least s . Define a mapping from each vertex v ∈ N ⩾ s G ( X ) to a clique of size exactly s in Q N [ G ( v ) ∩ X ] . At most t -1 vertices v ∈ N ⩾ s G ( X ) are mapped to each fixed s -clique in Q , as otherwise G contains K ∗ s,t (including the vertices matched to ( X 2 ) ). Hence | N ⩾ s G ( X ) | ⩽ ρ X | | +( t -1) ( ρ s -1 ) | X | = ( c -1) | X | .

Note that c s, t, ρ ( ) ⩽ tρ s -1 +1 .

Since K ∗ s,t contains K s,t , any result for K ∗ s,t -subgraph-free graphs is also applicable for K s,t -subgraph-free graphs. On the other hand, there is only a small difference between K ∗ s,t and K s,t since K s,t + ( ) s 2 contains K ∗ s,t . The advantage in considering K ∗ s,t over K s,t is improved dependence on t .

( )

Figure 5: The graph K ∗ 4 7 , .

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00983v1-figure-82eee9ff-9648-4fd4-9790-e96bb4b157c7.jpg)

## 3 Structural Results I

This section proves Theorem 2 from Section 1. Theorem 2 follows from the case S = ∅ in the following stronger result (Theorem 11) which has some additional properties. In particular, Property (2) of Theorem 11 is used in Section 5. The proof of Theorem 11 relies on a technical lemma (Lemma 12), which is stated and proved below.

Theorem 11. Fix s, t, ρ ∈ N and define c := c s, t, ρ ( ) as in Lemma 10. Then for any k ∈ N and any K ∗ s,t -subgraph-free graph G with tw( G ) ⩽ k -1 and ρ G ( ) ⩽ ρ , for any set S ⊆ V ( G ) with | S | ⩽ 12 ck , there exists a clean ( s -1) -quasi-tree-partition ( T, ( B x x ) ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) of G of width at most 18 ck , degree at most 6 c , and weight at most 12 k -1 , such that:

- (1) if z is the root of T then S ⊆ B z , and

̸

- (2) for every X ⊆ V ( G ) , if X has at least k +1 common neighbours in G , then there exists a vertical path in T passing through each node x ∈ V ( T ) with X ∩ B x = ∅ .

Proof. First assume that | V ( G ) | &lt; 4 k . Let T be the tree with V ( T ) = { x } and E T ( ) = ∅ . Let B x := V ( G ) . Let E v := ∅ for each v ∈ V ( G ) . Then (( B x ) x ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) is a clean 0 -quasiT -partition. The width is | B x | = | V ( G ) | &lt; 4 k ⩽ 18 ck , the degree is ∆( T ) = 0 ⩽ 6 c , and the weight is 0. Property (2) is trivial.

Now assume | V ( G ) | ⩾ 4 k . If | S | ⩾ 4 k then we are done by Lemma 12 below. Otherwise, let S ′ ⊆ V ( G ) with S ′ ⊇ S and | S ′ | = 4 k . The result now follows from Lemma 12 replacing S by S ′ .

The next lemma is the heart of the paper.

Lemma 12. Fix s, t, ρ ∈ N and define c := c s, t, ρ ( ) as in Lemma 10. Then for any k ∈ N , for any K ∗ s,t -subgraph-free graph G with tw( G ) ⩽ k -1 and ρ G ( ) ⩽ ρ , for any set S ⊆ V ( G ) with 4 k ⩽ | S | ⩽ 12 ck , there exists a clean ( s -1) -quasi-tree-partition ( T, ( B x ) x ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) of G of width at most 18 ck , degree at most 6 c , and weight at most 12 k -1 , such that:

- (1) if z is the root of T , then S ⊆ B z , | B z | ⩽ 3 2 | S | -2 k , and deg T ( z ) ⩽ | S | 2 k -1 , and

̸

- (2) for every X ⊆ V ( G ) , if X has at least k +1 common neighbours in G , then there is a vertical path in T passing through each node x ∈ V ( T ) with X ∩ B x = ∅ ,

Proof. We proceed by induction on the lexicographic order of ( | V ( G , V ) | | ( G ) \ S | ) .

Case 1. | V ( G ) \ S | ⩽ 18 ck : Let T be the 2-vertex tree with V ( T ) = { y, z } and E T ( ) = { yz } . Consider T to be rooted at z . Note that ∆( T ) = 1 ⩽ 6 c and deg T ( z ) = 1 ⩽ | S | 2 k -1 . Let B z := S and B y := V ( G ) \ S . Thus | B z | = | S | ⩽ 3 2 | S | -2 k ⩽ 18 ck and | B y | ⩽ | V ( G ) \ S | ⩽ 18 ck . Moreover, there exists a vertical path in T passing through each node of T . Let E v := ∅ for each v ∈ V ( G ) . So the loads satisfy C z = C y = ∅ , and the weight is 0. Thus (( B x x ) ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) is the desired clean ( s -1) -quasiT -partition of G .

Now assume that | V ( G ) \ S | ⩾ 18 ck . We first deal with the case when | S | is small.

Case 2. | V ( G ) \ S | ⩾ 18 ck and 4 k ⩽ | S | ⩽ 12 k -1 : Let u be any vertex in V ( G ) \ S , and let S ′ := S ∪{ }∪ u N ⩾ s G ( S ∪{ } u ) . By Lemma 10, | S ′ | ⩽ | S | +1+( c -1)( | S | +1) = c ( | S | +1) ⩽ 12 ck .

Since | S ′ | &gt; S | | ⩾ 4 k , by the induction hyposthesis, G has a clean ( s -1) -quasi-tree-partition ( T , ′ ( B ′ x ) x ∈ V ( T ′ ) , ( E ′ v ) v ∈ V ( G ) ) of width at most 18 ck , degree at most 6 c , and weight at most 12 k -1 such that:

- · if z ′ is the root of T , then S ′ ⊆ B ′ z ′ , | B ′ z ′ | ⩽ 3 2 | S ′ |-2 k ⩽ 18 ck , deg T ′ ( z ′ ) ⩽ | S ′ | 2 k -1 ⩽ 6 c -1 , and

̸

- · for every X ⊆ V ( G ) , if X has at least k +1 common neighbours in G , then there exists a vertical path in T ′ passing through each node x ∈ V ( T ′ ) with X ∩ B ′ x = ∅ .

Let C ′ x be the load of each x ∈ V ( T ′ ) , so | C ′ x | ⩽ 12 k -1 .

Let T be the tree obtained from T ′ by adding one new node z adjacent to z ′ . Consider z to be the root of T . Let B z := S and B z ′ := B ′ z ′ \ S and B x := B ′ x for each x ∈ V ( T ′ ) \ { z ′ } . For x ∈ V ( T ) , we have | B x | ⩽ max 18 { ck, | S |} ⩽ max 18 { ck, 12 k } = 18 ck . Hence the width bound is satisfied. Also, S = B z and | B z | = | S | ⩽ 3 2 | S | -2 k .

̸

Let E v := ∅ for each v ∈ B z ∪ B z ′ . For each child x of z ′ and for each v ∈ B x , let E v := { vw ∈ E G ( ) : w ∈ N G ( v ) ∩ B z } , which has size at most s -1 (since v ∈ B ′ z ′ ⊇ S ′ ⊇ N ⩾ s G ( S ) = N ⩾ s G ( B z ) ), and for each edge vw ∈ E v , w is in B y for some non-parent ancestor y of x in T ′ . For every other node x of T and for each v ∈ B x , let E v := E ′ v , which has size at most s -1 , and for each edge vw ∈ E v , w is in B y for some non-parent ancestor y of x in T ′ . Since B z ⊆ B ′ z ′ and each of z and z ′ has no non-parent ancestor, T := (( B x x ) ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) is a clean ( s -1) -quasiT -partition of G .

Now consider the degree of T . By construction, deg T ( z ) = 1 ⩽ | S | 2 k -1 and deg T ( z ′ ) = deg T ′ ( z ′ ) + 1 ⩽ (6 c -1) + 1 = 6 c . Every other vertex in T has the same degree as in T ′ . Hence ∆( T ) ⩽ 6 c , as desired.

Now consider the weight of T . Observe that C z = C z ′ = ∅ . For each child x of z ′ in T , we have C x ⊆ B z = S and thus | C x | ⩽ | S | ⩽ 12 k -1 . For every other node x of T , we have C x = C ′ x and thus | C x | = | C ′ x | ⩽ 12 k -1 . Hence T has weight at most 12 k -1 .

̸

̸

By construction, for every X ⊆ V ( G ) , if there exists a vertical path in T ′ passing through each node x ∈ V ( T ′ ) with X ∩ B ′ x = ∅ , then we can extend this path to be a vertical path in T from z such that it passes through all nodes x ∈ V ( T ) with X ∩ B x = ∅ . Hence (2) is satisfied.

Now we deal with the last case in the proof.

Case 3. | V ( G ) \ S | ⩾ 18 ck and 12 k ⩽ | S | ⩽ 12 ck : By the separator lemma of Robertson and Seymour [72, (2.6)], there are induced subgraphs G 1 and G 2 of G with G 1 ∪ G 2 = G and | V ( G 1 ∩ G 2 ) | ⩽ k , where | S ∩ V ( G i ) \ V ( G 3 -i ) | ⩽ 2 3 | S | for each i ∈ { 1 2 , } . Let S i := ( S ∩ V ( G i )) ∪ V ( G 1 ∩ G 2 ) for each i ∈ { 1 2 , } .

We now bound | S i | . For a lower bound, since | S ∩ V ( G 1 ) \ V ( G 2 ) | ⩽ 2 3 | S | , we have | S 2 | ⩾ | S ∩ V ( G 2 ) | ⩾ 1 3 | S | ⩾ 4 k . By symmetry, | S 1 | ⩾ 4 k . For an upper bound, | S i | ⩽ 2 3 | S | + k ⩽ 8 ck + k ⩽ 12 ck . Also note that | S 1 | + | S 2 | ⩽ | S | +2 k .

We have shown that 4 k ⩽ | S i | ⩽ 12 ck for each i ∈ { 1 2 , } . Thus, we may apply induction to G i with S i the specified set. Hence G i has a clean ( s -1) -quasi-tree-partition T i := ( T , i ( B i x ) x ∈ V ( T i ) , ( E i v ) v ∈ V ( G i ) ) of width at most 18 ck , degree at most 6 c , and weight at most 12 k -1 such that:

- · if z i is the root of T i then S i ⊆ B i z i , | B i z i | ⩽ 3 2 | S i | -2 k , and deg T i ( z i ) ⩽ | S i | 2 k -1 , and

̸

- · for every X ⊆ V ( G i ) , if X has at least k +1 common neighbours in G i , then there is a vertical path in T i passing through each node x ∈ V ( T i ) with X ∩ B i x = ∅ .

Let C i x be the load in T i of each node x ∈ V ( T i ) , so | C i x | ⩽ 12 k -1 .

Let T be the tree obtained from the disjoint union of T 1 and T 2 by merging z 1 and z 2 into a node z . Consider T to be rooted at z . Let B z := B 1 z 1 ∪ B 2 z 2 . Let B x := B i x for each x ∈ V ( T i ) \ { z i } .

Let E v := E i v for each v ∈ V ( G i ) . This is well-defined since V ( G 1 ∩ G 2 ) ⊆ B 1 z 1 ∩ B 2 z 2 , implying E 1 v = E 2 v = ∅ for each v ∈ V ( G 1 ∩ G 2 ) . By construction, for each v ∈ V ( G ) , if v ∈ B x for some x ∈ V ( T ) , then E v is a set of at most s -1 edges of G incident with v , and for each edge vw ∈ E v , w ∈ B y for some non-parent ancestor y of x in T . Since G = G 1 ∪ G 2 and V ( G 1 ∩ G 2 ) ⊆ B 1 z 1 ∩ B 2 z 2 ⊆ B z , we have that T := (( B x ) x ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) is a clean ( s -1) -quasiT -partition of G .

Consider the width of T . By construction, S ⊆ B z and since V ( G 1 ∩ G 2 ) ⊆ B i z i for each i ∈ [2] ,

$$\partial \text{ width of } V \,. \, \text{ By construction, } S \subseteq B _ { z } \text{ and since } V \left ( G _ { 1 } \left | \left | G _ { 2 } \right ) \subseteq B _ { z _ { i } } \text{ for } \\ | B _ { z } | & \leqslant | B _ { z _ { 1 } } ^ { 1 } | + | B _ { z _ { 2 } } ^ { 2 } | - | V ( G _ { 1 } \cap G _ { 2 } ) | \\ & \leqslant ( \frac { 3 } { 2 } | S _ { 1 } | - 2 k ) + ( \frac { 3 } { 2 } | S _ { 2 } | - 2 k ) - | V ( G _ { 1 } \cap G _ { 2 } ) | \\ & = \frac { 3 } { 2 } ( | S _ { 1 } | + | S _ { 2 } | ) - 4 k - | V ( G _ { 1 } \cap G _ { 2 } ) | \\ & \leqslant \frac { 3 } { 2 } ( | S | + 2 | V ( G _ { 1 } \cap G _ { 2 } ) | ) - 4 k - | V ( G _ { 1 } \cap G _ { 2 } ) | \\ & \leqslant \frac { 3 } { 2 } | S | + 2 | V ( G _ { 1 } \cap G _ { 2 } ) | - 4 k \\ & \leqslant \frac { 3 } { 2 } | S | - 2 k \\ & < 1 8 c k. \\ \text{ nart has the same size as in } \mathcal { T } ^ { 1 } \text{ or } \mathcal { T } ^ { 2 } \text{ } S \in | R | < 1 8 c k \text{ for each } r \in \mathcal { L }$$

Every other part has the same size as in T 1 or T 2 . So | B x | ⩽ 18 ck for each x ∈ V ( T ) .

Now consider the degree of T . Note that

$$\text{source} \, \text{glyvel} \, \text{$0$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$}} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \                                                                                                                                                                                                        
                                                                                                                                                                                                        \text{glyvel} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \, \text{$1$} \\ \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \tau \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \tau \, \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{Glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyVEL} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel} \, \quad \text{glyvel}$$

Every other node of T has the same degree as in T 1 or T 2 . Thus ∆( T ) ⩽ 6 c .

Finally, consider the weight of T . Let C x be the load of each x ∈ V ( T ) . Since z is the root, C z = ∅ . For each node x ∈ V ( T i ) \ { z i } , we have C x = C i x , so | C x | ⩽ 12 k -1 . Hence T has weight at most 12 k -1 .

̸

̸

Let X be an arbitrary subset of V ( G ) such that nodes in X have at least k + 1 common neighbours in G . If X \ V ( G 1 ) = ∅ ̸ = X \ V ( G 2 ) , then all of the at least k + 1 common neighbours of X are contained in V ( G 1 ∩ G 2 ) , which is a set with size at most k , a contradiction. Hence there exists i ∈ [2] such that X ⊆ V ( G i ) . So every node x ∈ V ( T ) with X ∩ B x = ∅ is a node of T i with X ∩ B i x = ∅ . If X has at least k +1 common neighbours in G i , then there exists

̸

̸

̸

a vertical path in T i (and hence in T ) passing through each node x ∈ V ( T ) with X ∩ B x = ∅ . If X does not have at least k +1 common neighbours in G i , then at least one common neighbour of X is contained in V ( G 3 -i ) \ V ( G i ) , so X ⊆ V ( G 1 ∩ G 2 ) ⊆ B z , so the path consisting of z is a vertical path in T passing through each node x ∈ V ( T ) with X ∩ B x = ∅ . This completes the proof.

The next result is a more precise version of Corollary 3. It follows from Theorem 11 and (3) since ρ G ( ) ⩽ tw( G ) ⩽ k -1 , implying c ⩽ tk s -1 .

Corollary 13. For any k, s, t ∈ N , any K ∗ s,t -subgraph-free graph G with tw( G ) ⩽ k -1 has a clean ( s -1) -quasi-tree-partition of width at most 18 tk s , degree at most 6 tk s -1 , and weight at most 12 k -1 .

Corollary 13 with s = 1 recovers Theorem 1 for tree-partitions of graphs with given tree-width and maximum degree, and also recovers the degree bound in [21, 22] mentioned above.

We now give more examples of Theorem 2. First consider K t -minor-free graphs G . Here G is K t -1 ,t -1 -subgraph-free, since contracting a matching in K t -1 ,t -1 with size t -2 gives K t . It follows from a result of Kostochka [54, 55] and Thomason [75, 76] that ρ G ( ) ∈ O t ( √ log t ) . And Alon, Seymour, and Thomas [2] showed that tw( G ) ⩽ t 3 2 / | V ( G ) | 1 2 / . The next result thus follows directly from the S = ∅ case of Theorem 11.

Corollary 14. For any t ∈ N there exists c 1 , . . . , c 5 ∈ N such that every K t -minor-free graph G has a clean ( t -2) -quasi-tree-partition of width at most c 1 tw( G ) ⩽ c 2 | V ( G ) | 1 2 / , degree at most c 3 , and weight at most c 4 tw( G ) ⩽ c 5 | V ( G ) | 1 2 / .

Theorem 2 is also applicable and interesting for non-minor-closed classes. The following definitions by Dujmović, Morin, and Wood [28] are useful for this purpose. A layering of a graph G is an ordered partition ( V , V 1 2 , . . . ) of V ( G ) such that for each edge vw ∈ E G ( ) , if v ∈ V i and w ∈ V j then | i - | j ⩽ 1 . The layered tree-width ltw( G ) of a graph G is the minimum k ∈ N such that G has a layering ( V , V 1 2 , . . . ) and a tree-decomposition ( T, ( B x ) x ∈ V ( T ) ) such that | V i ∩ B x | ⩽ k for each i ∈ N and x ∈ V ( T ) . For example, Dujmović et al. [28] proved that every planar graph has layered tree-width at most 3; more generally, every graph with Euler genus g has layered tree-width at most 2 g +3 ; and most generally, a minor-closed class G has bounded layered tree-width if and only if some apex graph is not in G . Dujmović et al. [28, Lemma 8] noted in its proof that for every graph G ,

$$\delta ( G ) \leqslant 3 \, \text{ltw} ( G ) - 1.$$

The next lemma is proved using an idea from [28, Lemma 9].

Lemma 15. For every graph G ,

$$\rho ( G ) \leqslant 6 \, \text{ltw} ( G ) - 1.$$

Proof. Let k := ltw( G ) . Say H is a graph such that the 1-subdivision H ′ of H is a subgraph of G . So ltw( H ′ ) ⩽ k . Consider a layering and tree-decomposition of H ′ such that each layer has at most k vertices in each bag. For each vertex x of H ′ obtained by subdividing an edge vw of H ,

replace each instance of x in the tree-decomposition of H ′ by v . We obtain a tree-decomposition of H without increasing the bag size. In the layering of H ′ , group pairs of consecutive layers to produce a layering of H . Hence, ltw( H ) ⩽ 2 k , and δ H ( ) ⩽ 3 · 2 k -1 = 6 k -1 . This says that ρ G ( ) ⩽ 6 k -1 .

Several non-minor-closed graph classes are known to have bounded layered tree-width [24, 28]. Here is one example. For g, k ∈ N 0 , a graph is ( g, k ) -planar if it has a drawing in a surface of Euler genus at most g such that each edge contains at most k crossings. Every ( g, k ) -planar graph G has layered tree-width at most 2(2 g + 3)( k + 1) [24], and thus ρ G ( ) ⩽ 12(2 g + 3)( k + 1) -1 by Lemma 15. Also, G is K 3 (24 , k +1)(2 +2)+13 g -subgraph-free [49] and tw( G ) ∈ O ( √ ( g +1)( k +1) | V ( G ) ) | [24]. Thus the S = ∅ case of Theorem 11 with s = 3 implies:

Corollary 16. There exists c 1 , . . . , c 5 ∈ N such that for any g, k ∈ N 0 every ( g, k ) -planar graph G has a clean 2 -quasi-tree-partition with:

- · width at most c 1 ( g +1) ( 3 k +1) tw( 3 G ) ⩽ c 2 ( g +1) 7 2 / ( k +1) 7 2 / | V ( G ) | 1 2 / ,
- · degree at most c 3 ( g +1) ( 3 k +1) 3 , and
- · weight at most c 4 tw( G ) ⩽ c 5 ( g +1) 1 2 / ( k +1) 1 2 / | V ( G ) | 1 2 / .

Note that Corollary 4 is the special case k = 0 of Corollary 16 (with lightly worse dependence on g )

## 4 Defective and Clustered Colouring

This section presents applications of our structural results from the previous section for graph colouring.

A colouring of a graph G is simply a function f : V ( G ) →C for some set C whose elements are called colours . If |C| ⩽ k then f is a k -colouring . An edge vw of G is f -monochromatic if f ( v ) = f ( w ) . A colouring f is proper if no edge is f -monochromatic. An f -monochromatic component , sometimes called a monochromatic component , is a connected component of the subgraph of G induced by { v ∈ V ( G ) : f ( v ) = α } for some colour α ∈ C . We say f has clustering c if every f -monochromatic component has at most c vertices. The f -monochromatic degree of a vertex v is the degree of v in the monochromatic component containing v . Then f has defect d if every f -monochromatic component has maximum degree at most d (that is, each vertex has monochromatic degree at most d ).

The clustered chromatic number χ ⋆ ( G ) of a graph class G is the infimum of the set of nonnegative integers k such that for some c ∈ N every graph in G has a k -colouring with clustering c . The defective chromatic number χ ∆ ( G ) of a graph class G is the infimum of the set of nonnegative integers k such that for some d ∈ N 0 every graph in G has a k -colouring with defect d . Every colouring of a graph with clustering c has defect c -1 . Thus χ ∆ ( G ) ⩽ χ ⋆ ( G ) ⩽ χ ( G ) for every class G , where χ ( G ) is the infimum of the set of nonnegative integers k such that every graph in G has a proper k -colouring.

Clustered and defective colouring have recently been widely studied [15-17, 26, 33, 34, 3638, 40, 48, 51, 52, 57-63, 65-67, 77, 81]; see [82] for a survey.

## 4.1 List Colouring

A list-assignment for a graph G is a function L that assigns a set L v ( ) of colours to each vertex v ∈ V ( G ) . A graph G is L -colourable if there is a proper colouring of G such that each vertex v ∈ V ( G ) is assigned a colour in L v ( ) . A list-assignment L is a k -list assignment if | L v ( ) | ⩾ k for each vertex v ∈ V ( G ) . The list-chromatic-number χ ℓ ( G ) of a graph G is the minimum k ∈ N 0 such that G is L -colourable for every k -list-assignment L of G .

For a list-assignment L of a graph G and d ∈ N 0 , define G to be L -colourable with defect d if there is a colouring of G with defect d such that each vertex v ∈ V ( G ) is assigned a colour in L v ( ) . Define G to be k -list-colourable with defect d if G is L -colourable with defect d for every k -list assignment L of G . Similarly, for c ∈ N , G is L -colourable with clustering c if there is a colouring of G with clustering c such that each vertex v ∈ V ( G ) is assigned a colour in L v ( ) . Define G to be k -list-colourable with clustering c if G is L -colourable with clustering c for every k -list assignment L of G .

The defective list-chromatic-number of a graph class G , denoted by χ ℓ ∆ ( G ) , is the infimum k ∈ N such that for some d ∈ N every graph in G is k -list-colourable with defect d . The clustered list-chromatic-number χ ℓ ⋆ ( G ) of a graph class G is the infimum k ∈ N such that for some c ∈ N every graph in G is k -list-colourable with clustering c .

Ossona de Mendez et al. [69] proved the following result about defective colouring and sparsity. For a graph G , let ∇ ( G ) be the maximum of | E H ( ) | | V ( H ) | , taken over all graphs H such that some ( ⩽ 1) -subdivision of H is a subgraph of G . (Note that ∇ ( G ) ⩽ ρ G ( ) ⩽ 2 ∇ ( G ) since | E H ( ) | | V ( H ) | ⩽ δ H ( ) ⩽ 2 | E H ( ) | | V ( H ) | .)

Theorem 17 ([69]) . For any s, t ∈ N and ∇ ∈ R &gt; 0 there exists d ∈ N such that every K ∗ s,t -subgraph-free graph G with ∇ ( G ) ⩽ ∇ is s -list-colourable with defect d .

A balanced separator in a graph G is a set X ⊆ V ( G ) such that every component of G -X has at most | V ( G ) | 2 vertices. For a function f : N → R ⩾ 0 , a graph G admits f -separators if every induced subgraph H of G has a balanced separator in H of size at most f ( | V ( H ) ) | . A graph class G admits strongly sublinear separators if there exists a function f with f ( n ) ∈ O n ( β ) for some fixed β ∈ [0 , 1) such that every graph in G admits f -separators. If G admits strongly sublinear separators, then G has bounded ∇ [32, 39]. Theorem 17 thus implies:

̸

$$\chi _ { \Delta } ( \mathcal { G } ) \leqslant \chi _ { \Delta } ^ { \ell } ( \mathcal { G } ) \leqslant s.$$

Corollary 18. For every monotone graph class G admitting strongly sublinear separators and with K ∗ s,t ∈ G ,

The authors proved the following result in a previous paper.

Theorem 19 ([60]) . For k, s, t ∈ N with t ⩾ s , there exists c ∈ N such that every K s,t -subgraphfree graph with tree-width at most k is ( s +1) -list-colourable with clustering c .

The proof of Theorem 19 also works for K ∗ s,t -subgraph-free graphs. Our structure theorem (Theorem 11) can be used to prove Theorem 19. In fact, we use Theorem 11 to prove a more general 'fractional' version below (Theorem 25). Also note that s +1 colours in Theorem 19 is best possible [60]. Since Theorem 11 implies Theorem 19, this says that the ' ( s -1) -quasi' term in Theorems 2 and 11 and Corollary 3 is also best possible.

## 4.2 Fractional Colouring

Let G be a graph. For p, q ∈ N with p ⩾ q , a p q : -colouring of G is a function ϕ : V ( G ) → ( C q ) for some set C with | C | = p . That is, each vertex is assigned a set of q colours out of a palette of p colours. For t ∈ R , a fractional t -colouring is a p q : -colouring for some p, q ∈ N with p q ⩽ t . A p q : -colouring ϕ of G is proper if ϕ v ( ) ∩ ϕ w ( ) = ∅ for each edge vw ∈ E G ( ) .

The fractional chromatic number of G is

χ f ( G ) := inf { t ∈ R : G has a proper fractional t -colouring } .

The fractional chromatic number is widely studied; see the textbook [73], which includes a proof of the fundamental property that χ f ( G ) ∈ Q .

Fractional 1-defective colourings were first studied by Farkasová and Soták [41]; see [45, 53, 64] for related results. Fractional defective and clustered colouring (with general bounds on the defect and clustering) were introduced by Dvořák and Sereni [34] and subsequently studied by Norin et al. [67] and Esperet and Wood [40]. For a p q : -colouring f : V ( G ) → ( C q ) of G and for each colour α ∈ C , the subgraph G v [ { ∈ V ( G ) : α ∈ f ( v ) } ] is called an f -monochromatic subgraph or monochromatic subgraph when f is clear from the context. A connected component of an f -monochromatic subgraph is called an f -monochromatic component or monochromatic component . Note that f is proper if and only if each f -monochromatic component has exactly one vertex.

A p q : -colouring has defect d if every monochromatic subgraph has maximum degree at most d . A p q : -colouring has clustering c if every monochromatic component has at most c vertices.

The fractional defective chromatic number χ f ∆ ( G ) of a graph class G is the infimum of all t &gt; 0 such that, for some d ∈ N every graph in G is fractionally t -colourable with defect d . The fractional clustered chromatic number χ f ⋆ ( G ) of a graph class G is the infimum of all t &gt; 0 such that, for some c ∈ N , every graph in G is fractionally t -colourable with clustering c .

For k, n ∈ N , let T k,n be the rooted tree in which every leaf is at distance k -1 from the root, and every non-leaf has n children. Let C k,n be the graph obtained from T k,n by adding an edge between every pair of two vertices, where one is an ancestor of the other (called the closure of T k,n ). Colouring each vertex by its distance from the root gives a k -colouring of C k,n , and any root-leaf path in C k,n induces a k -clique. So χ C ( k,n ) = k . The class C k := { C k,n : n ∈ N } is important for defective and clustered colouring, and is often called the 'standard' example. It is well-known and easily proved (see [82]) that

$$\chi _ { \Delta } ( \mathcal { C } _ { k } ) = \chi _ { * } ( \mathcal { C } _ { k } ) = \chi ( \mathcal { C } _ { k } ) = k.$$

Norin et al. [67] extended this result (using a result of Dvořák and Sereni [34]) to the setting of defective and clustered fractional chromatic number by showing that

$$\chi _ { \Delta } ^ { f } ( \mathcal { C } _ { k } ) = \chi _ { * } ^ { f } ( \mathcal { C } _ { k } ) = \chi ^ { f } ( \mathcal { C } _ { k } ) = \chi _ { \Delta } ( \mathcal { C } _ { k } ) = \chi _ { * } ( \mathcal { C } _ { k } ) = \chi ( \mathcal { C } _ { k } ) = k.$$

Let ω ∆ ( G ) := sup { k ∈ N : |G ∩ C k | = ∞} . Hence (6) implies that for every graph class G ,

$$\chi _ { * } ( \mathcal { G } ) \geqslant \max \{ \chi _ { \Delta } ( \mathcal { G } ), \chi _ { * } ^ { f } ( \mathcal { G } ) \} \geqslant \min \{ \chi _ { \Delta } ( \mathcal { G } ), \chi _ { * } ^ { f } ( \mathcal { G } ) \} \geqslant \chi _ { \Delta } ^ { f } ( \mathcal { G } ) \geqslant \omega _ { \Delta } ( \mathcal { G } ).$$

For every proper minor-closed class G , Norin et al. [67] showed that

$$\chi ^ { f } _ { \Delta } ( \mathcal { G } ) = \chi ^ { f } _ { * } ( \mathcal { G } ) = \omega _ { \Delta } ( \mathcal { G } ),$$

and Liu [58] strengthened it by showing that

$$\chi _ { \Delta } ( \mathcal { G } ) = \omega _ { \Delta } ( \mathcal { G } ).$$

As another example, the result of Norin et al. [67] implies that the class of graphs embeddable in any fixed surface has fractional clustered chromatic number and fractional defective chromatic number 3.

Assuming bounded maximum degree, Dvořák [31] and Dvořák and Sereni [34] proved the following stronger results 1 :

Theorem 20 ([31, 34]) . Let f : N → R ⩾ 0 be a function such that f n ( ) ∈ O n ( β ) for some fixed β ∈ [0 , 1) . Then for any ∆ ∈ N and ϵ ∈ R &gt; 0 , there exist p, q, c ∈ N with p ⩽ (1 + ϵ q ) such that every graph of maximum degree at most ∆ admitting f -separators is p q : -colourable with clustering c .

Corollary 21 ([31, 34]) . Every hereditary graph class admitting strongly sublinear separators and with bounded maximum degree has fractional clustered chromatic number 1.

These results lead to the following.

Corollary 22. For every hereditary graph class G admitting strongly sublinear separators,

$$\chi _ { \Delta } ^ { f } ( \mathcal { G } ) = \chi _ { * } ^ { f } ( \mathcal { G } ).$$

Proof. It follows from the definitions that χ f ∆ ( G ) ⩽ χ f ⋆ ( G ) . We now prove that χ f ⋆ ( G ) ⩽ χ f ∆ ( G ) . Fix a graph G . Let k := χ f ∆ ( G ) . Thus, for each ϵ &gt; 0 , there exist p, q, d ∈ N with p ⩽ ( k + ) ϵ q such that d only depends on G and ϵ , and G is p q : -colourable with defect d . By Theorem 20, for each ϵ ′ &gt; 0 , there exist p , q , c ′ ′ ∈ N with p ′ ⩽ (1 + ϵ ′ ) q ′ such that c only depends on G , d and ϵ ′ , and every monochromatic subgraph of G (under the first colouring) is p ′ : q ′ -colourable with clustering c . Taking a product colouring, we find that G is pp ′ : qq ′ -colourable with clustering c . Now, pp ′ ⩽ ( k + )(1 + ϵ ϵ ′ ) qq ′ . We may choose ϵ and ϵ ′ so that ( k + )(1 + ϵ ϵ ′ ) is arbitrarily close to k . So χ f ⋆ ( G ) ⩽ k .

1 Theorem 20 is not explicitly stated in [31, 34], but it can be concluded from Lemma 19 in [31] (restated as Theorem 15 in [34]) and Lemma 2 in [34] where f ( G ) is the maximum order of a component of G .

Corollaries 18 and 22 immediately imply:

̸

Corollary 23. If G is a monotone graph class admitting strongly sublinear separators and with K ∗ s,t ∈ G , then

$$\chi _ { * } ^ { f } ( \mathcal { G } ) = \chi _ { \Delta } ^ { f } ( \mathcal { G } ) \leqslant \chi _ { \Delta } ( \mathcal { G } ) \leqslant s.$$

̸

Note that Corollary 23 implies the upper bound of the above-mentioned result of Norin et al. [67] which says that if G is the class of graphs with Euler genus g , then χ f ⋆ ( G ) = χ f ∆ ( G ) = 3 (since K 3 2 , g +3 ∈ G ). In fact, the following more general result follows from Corollary 23 since the class of ( g, k ) -planar graphs is monotone, admits O ( √ ( g +1)( k +1) ) n separators (see [24]), and does not contain K 3 (24 , k +1)(2 +2)+13 g (see [49]):

Corollary 24. For any g, k ∈ N 0 , if G g,k is the class of ( g, k ) -planar graphs, then

$$\chi _ { * } ^ { f } ( \mathcal { G } _ { g, k } ) = \chi _ { \Delta } ^ { f } ( \mathcal { G } _ { g, k } ) = \chi _ { \Delta } ( \mathcal { G } _ { g, k } ) = 3.$$

## 4.3 Fractional List Colouring

We now show how to use our structural result about quasi-tree-partitions to strengthen Corollary 23 to choosability for graphs with bounded tree-width.

For a list-assignment L of a graph G , an L q : -colouring of G is a function ϕ such that ϕ v ( ) is a q -element subset of L v ( ) for each vertex v of G . A graph G is p q : -list-colourable with clustering c if for every p -list-assignment L of G , there is an L q : -colouring of G with clustering c .

The following is the main result of this subsection, where the non-fractional ( ℓ = 1 ) case (Theorem 19) was proved by the authors [61].

Theorem 25. For any k, s, t, ℓ ∈ N there exists c ∈ N such that every K ∗ s,t -subgraph-free graph with tree-width at most k is ( ℓs +1) : ℓ -list-colourable with clustering c .

Theorem 25 follows from Theorem 11 and the next lemma.

Lemma 26. For any s, ℓ, k, d ∈ N , if a graph G has a clean ( s -1) -quasi-tree-partition of width at most k and degree at most d , then G is ( ℓs + 1) : ℓ -list-colourable with clustering max { ℓk , 2 2 kd ℓk -1 } .

Proof. Let L be an ( ℓs +1) -list assignment for G . We may assume that L v ( ) ⊆ N for each v ∈ V ( G ) . By assumption, there exists ( E v ⊆ E G ( ) : v ∈ V ( G )) with | E v | ⩽ s -1 for each v ∈ V ( G ) , such that G -⋃ v ∈ V ( G ) E v has a T -partition ( B x ) x ∈ V ( T ) of width at most k and degree at most d , and for each v ∈ V ( G ) and for each edge vw ∈ E v , if v ∈ B x and w ∈ B y , then y is a non-parent ancestor of x in T . We add edges to G so that B x ∪ B y is a clique for each edge xy ∈ E T ( ) . To prove this lemma, it suffices to show that G has an L p : -colouring.

Let z be the root of T . Let ⪯ T be a total order on V ( T ) where for all x, y ∈ V ( T ) , if dist T ( z, x ) ⩽ dist T ( z, y ) then x ⪯ T y . Let ⪯ G be a total order on V ( G ) where for all v, w ∈ V ( G ) , if v ∈ B x and w ∈ B y and x ⪯ T y , then v ⪯ G w . Finally, let ⪯ be a total

order on X := { ( v, i ) : v ∈ V ( G , i ) ∈ L v ( ) } , where for all ( v, i ) , ( w,j ) ∈ X , if v ⪯ G w then ( v, i ) ⪯ ( w,j ) , and if v = w and i &lt; j , then ( v, i ) ≺ ( w,j ) .

We will colour the vertices of G in order of ⪯ G . For any monochromatic subgraphs A and B of some partially coloured induced subgraph of G , we say that A is older than B if ( v A , i A ) ≺ ( v B , i B ) , where for every C ∈ { A,B } , i C is the colour of C , and v C is the minimum vertex in C with respect to ⪯ G .

Colour the vertices of G in order of ⪯ G , where each vertex v is assigned a set of ℓ colours in L v ( ) distinct from the ℓ colours assigned to the end (distinct from v ) of each edge in E v , and distinct from the colour of the currently oldest monochromatic component adjacent in G -⋃ u ∈ V ( G ) E u to v . Such a colouring exists, since | L v ( ) | -ℓ E | v | -1 ⩾ | L v ( ) | -ℓ s ( -1) -1 ⩾ ℓ .

Since for each v ∈ V ( G ) , the ends of each edge in E v are assigned disjoint sets of colours, if vw is any monochromatic edge of G with v ∈ B x and w ∈ B y then x = y or xy ∈ E T ( ) . That is, monochromatic edges of G map to vertices or edges of T . This implies that when colouring a vertex v , since B x ∪ B y is a clique for each edge xy ∈ E T ( ) , no two distinct pre-existing monochromatic components are merged into one monochromatic component. So colouring a vertex does not change the older relationship between pre-existing monochromatic components. That is, if C 1 and C 2 are distinct monochromatic components at some point, and C 1 is older than C 2 at this point, then at any later time, the monochromatic component containing C 1 is older than the monochromatic component containing C 2 .

Consider an edge xy ∈ E T ( ) with x the parent of y . Say C is the j -th oldest monochromatic component intersecting B x immediately after all the vertices in B x have been coloured, where j ⩽ ℓ B | x | ⩽ ℓk . Note that when colouring vertices in B y , C is always contained in the j -th oldest monochromatic component intersecting B x (although this j -th oldest monochromatic component intersecting B x can change from time to time). When colouring vertices in B y , by the above colouring procedure, the oldest monochromatic component intersecting B x cannot intersect B y . So after colouring all the vertices in B y , if the monochromatic component C ′ containing C intersects B y , then C ′ is the i -th oldest monochromatic component intersecting B y , for some i ⩽ j -1 .

Now we bound the clustering of the colouring. Let M be a monochromatic component when all vertices of G are coloured. Assume that M intersects all of B x 1 , . . . , B x p , where x i is the parent of x i +1 for each i ∈ { 1 , . . . , p } . For each i ∈ { 1 , . . . , p } , let d i be the smallest integer such that when we just finished colouring all vertices of x i , the d i -th oldest component intersecting B x i is contained in M . Then d 1 ⩽ ℓk , and d i ⩽ d i -1 -1 for each i ∈ { 2 , . . . , p } . Thus 1 ⩽ d p ⩽ d 1 -p + 1 ⩽ ℓk -p + 1 , implying p ⩽ ℓk . Since ∆( T ) ⩽ d and | B x | ⩽ k for each x ∈ V ( T ) , we have | V ( M ) | ⩽ k (1 + d + d 2 + · · · + d ℓk -1 ) . Note that if d ⩾ 2 , then (1 + d + d 2 + · · · + d ℓk -1 ) ⩽ 2 d ℓk -1 . So | V ( M ) | ⩽ max { ℓk , 2 2 kd ℓk -1 } .

## 5 Structural Results II

This section establishes extensions of the structural results in Section 3 for graphs containing no 1-extension of K s,a and no skewered K s,b .

Lemma 27. Let s, a, b ∈ N with a ⩾ 2 . For any graph G and set X ⊆ V ( G ) with | X | = s , if some component C of G -X contains at least ( a -1)( b -1) + 1 vertices in N ⩾ s G ( X ) , then G contains a 1-extension of K s,a or a skewered K s,b .

Proof. Let T be a spanning tree of C rooted at a vertex r in N ⩾ s G ( X ) . If there exists a path P in T from r containing b vertices in N ⩾ s G ( X ) , then G X [ ∪ V ( P )] contains a skewered K s,b . So we may assume that every path in T from r contains at most b -1 vertices in N ⩾ s G ( X ) . In particular, b ⩾ 2 .

̸

Define a poset Q = ( N ⩾ s G ( X ) ∩ V ( C , ) ⪯ ) such that for any two elements x, y in the ground set, x ⪯ y if and only if x = y or x is an ancestor of y in T . Since every path in T from r contains at most b -1 vertices in N ⩾ s G ( X ) , every chain of Q has size at most b -1 . By Dilworth's Theorem, Q has an antichain A of size ⌈| N ⩾ s G ( X ) ∩ V ( C ) | / b ( -1) ⌉ ⩾ a . Since a ⩾ 2 , r ∈ A . Let T ′ be the subtree of T consisting of all paths from r to the parents of vertices in A . Contracting T ′ into a vertex, and deleting vertices not in X ∪ V ( T ′ ) ∪ A gives a 1-extension of K s,a .

If ( B x x ) ∈ V ( T ) is a partition of a graph G indexed by a rooted tree T , then a node y ∈ V ( T ) is s -heavy (with respect to ( B x ) x ∈ V ( T ) ) if | N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q | ⩾ s .

Theorem 28. Fix k, s, a, b, ρ ∈ N with a, b ⩾ 2 . Let t := ( s +( a -1)( b -1))( a -1)( b -1)+ k +1 . Define c := c s, t, ρ ( ) as in Lemma 10. If G is a graph with tw( G ) ⩽ k -1 and ρ G ( ) ⩽ ρ that contains no 1-extension of K s,a and no skewered K s,b , then for any set S ⊆ V ( G ) with | S | ⩽ s +( a -1)( b -1) , there exists a clean ( s -1) -quasi-tree-partition ( T, ( B x x ) ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) of G of width at most 18 ck such that:

- · if z is the root of T , then S ⊆ B z ,
- · every node in T has at most 6 c ( s +1) -heavy children, and

̸

- · for every Y ⊆ V ( G ) , if Y has at least max { k +1 , s +1 } common neighbours in G , then there exists a vertical path in T passing through each node x ∈ V ( T ) with Y ∩ B x = ∅ .

Proof. We proceed by induction on | V ( G ) | . If G is K s,t -subgraph-free, then the result follows from Theorem 11 (since | S | ⩽ s + ( a -1)( b -1) ⩽ t ⩽ c ⩽ 12 ck ). This proves the base case. Now assume that G contains K s,t . Hence there exists X ⊆ V ( G ) with | X | = s with | N ⩾ s G ( X ) | ⩾ t .

By Lemma 27, every component of G -X contains at most ( a -1)( b -1) vertices in N ⩾ s G ( X ) . So G -X contains at least ⌈ t ( a -1)( b -1) ⌉ ⩾ s +( a -1)( b -1) + 1 ⩾ | S | +1 components. Hence there exists a component C of G -X disjoint from S . By induction, G -V ( C ) has a clean ( s -1) -quasi-tree-partition ( T , 1 ( B 1 x x ) ∈ V ( T 1 ) , ( E 1 v ) v ∈ V ( G V C -( )) ) of width at most 18 ck such that

- · if z 1 is the root of T 1 , then S ⊆ B 1 z 1 ,
- · every node of T 1 has at most 6 c ( s +1) -heavy children, and

̸

- · for every Y ⊆ V ( G ) -V ( C ) , if Y has at least max { k +1 , s +1 } common neighbours in G -V ( C ) , then there exists a vertical path in T 1 passing through each node x ∈ V ( T 1 ) with Y ∩ B 1 x = ∅ .

Let S ′ := X ∪ ( N ⩾ s G ( X ) ∩ V ( C )) . Note that | S ′ | = | X | + | N ⩾ s G ( X ) ∩ V ( C ) | ⩽ s +( a -1)( b -1) by Lemma 27. By induction applied to G V [ ( C ) ∪ X ] with S ′ the specified set, G V [ ( C ) ∪ X ]

has a clean ( s -1) -quasi-tree-partition ( T , 2 ( B 2 x x ) ∈ V ( T 2 ) , ( E 2 v ) v ∈ V ( C ) ∪ X ) of width at most 18 ck such that

- · if z 2 is the root of T 2 then S ′ ⊆ B 2 z 2 ,
- · every node of T 2 has at most 6 c ( s +1) -heavy children, and

̸

- · for every Y ⊆ X ∪ V ( C ) , if Y has at least max { k +1 , s +1 } common neighbours in G X [ ∪ V ( C )] , then there exists a vertical path in T 2 passing through each node x ∈ V ( T 2 ) with Y ∩ B 2 x = ∅ .

Note that E 2 v = ∅ for each v ∈ B 2 z 2 , since z 2 has no parent in T 2 . Similarly, for each child x of z 2 , we may assume that E 2 v = ∅ for each v ∈ B 2 x .

Let T 3 be the tree obtained from T 2 by adding a new node z 3 adjacent to z 2 . Consider T 3 to be rooted at z 3 . Let B 3 z 3 := X , and let B 3 z 2 := B 2 z 2 \ X . For each x ∈ V ( T 2 ) \ { z 2 } , let B 3 x := B 2 x . For each x ∈ V ( T 2 ) that is not a child of z 2 and for each v ∈ B 3 x , let E 3 v := E 2 v . For each x ∈ V ( T 2 ) that is a child of z 2 and for every v ∈ B 3 x , let E 3 v be the set of edges between v and X . By construction, ( B 3 x ) x ∈ V ( T 3 ) is a tree-partition of G X [ ∪ V ( C )] -⋃ v ∈ X V C ∪ ( ) E 3 v . Since N ⩾ s G ( X ) ∩ V ( C ) ⊆ S ′ ⊆ B 2 z 2 , E 3 v is a set of at most s -1 edges of G V [ ( C ) ∪ X ] incident with v for every v ∈ V ( C ) .

̸

̸

̸

Note that X has at least t common neighbours in G , and V ( C ) contains at most ( a -1)( b -1) common neighbours of X . So X has at least t -( a -1)( b -1) = ( s -1 + ( a -1)( b -1))( a -1)( b -1) + k +1 ⩾ s + k ⩾ max { k +1 , s +1 } common neighbours in G -V ( C ) . Thus, there exists a vertical path P in T 1 passing through each node x ∈ V ( T 1 ) with X ∩ B x = ∅ . Let z ∗ be the vertex of P furtherest from z 1 such that X ∩ B 1 z ∗ = ∅ . Thus each vertex x ∈ V ( T 1 ) with X ∩ B 1 x = ∅ is an ancestor of z ∗ or equal to z ∗ .

Let T be the tree obtained from the disjoint union of T 1 and T 3 by identifying z ∗ and z 3 . Consider T to be rooted at z 1 . So the parent of z 3 in T is the parent of z ∗ in T 1 . For each x ∈ V ( T 1 ) , let B x := B 1 x . For each x ∈ V ( T 3 ) -{ z 3 } , let B x := B 3 x . Then ( B x ) x ∈ V ( T ) is a partition of V ( G ) of width at most 18 ck , and S ⊆ B z 1 .

For each v ∈ V ( G ) -V ( C ) , let E v := E 1 v . For each v ∈ V ( C ) -B 2 z 2 , let E v := E 3 v . By construction, for every v ∈ V ( G ) -( B 2 z 2 -X ) , E v is a set of at most s -1 edges incident with v , and for each edge vw ∈ E v , if v ∈ B x and w ∈ B y , then by the choice of z ∗ , y is a non-parent ancestor of x .

̸

For each v ∈ B 2 z 2 -X , let E v be the set of edges between v and X -B 1 z ∗ . Since X ∩ B 1 z ∗ = ∅ , we know | X -B 1 z ∗ | ⩽ | X | -1 ⩽ s -1 , so v ∈ N ⩽ s -1 G ( X -B 1 z ∗ ) for every v ∈ V ( C ) . Hence | E v | ⩽ s -1 for every v ∈ V ( G ) . And by the choice of z ∗ , for every v ∈ B 2 z 2 -X and for each edge vw ∈ E v , if v ∈ B x and w ∈ B y , then y is a non-parent ancestor of x .

By the definition of E v for v ∈ B 2 z 2 -X , we know ( B x x ) ∈ V ( T ) is a T -partition of G -⋃ v ∈ V ( G ) E v . Hence (( B x x ) ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) is a clean ( s -1) -quasiT -partition of G of width at most 18 ck .

̸

We now prove the claim about the number of heavy children of a node in T . For each x ∈ V ( T 1 ) and child y of x in T 1 , if X ∩ B 1 y = ∅ , then N G ( B y ) = N G ( B 1 y ) ⊆ V ( G ) -V ( C ) , so | N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q | = | N G ( B 1 y ) ∩ ⋃ q ∈ T 1 ↑ y B 1 q | ; if X ∩ B 1 y = ∅ , then by the choice of z ∗ , T ↑ y is disjoint from V ( T 2 ) and hence equal to T 1 ↑ y , so | N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q | =

| N G ( B 1 y ) ∩ ⋃ q ∈ T 1 ↑ y B 1 q | . If x ∈ V ( T 1 ) and y is a child of x in T but not in T 1 , then x = z ∗ and y = z 2 , so N G ( B y ) ⊆ X ∪ V ( C ) , and hence N G ( B y ) ∩ ⋃ q ∈ T ↑ y ⊆ X , which has size s &lt; s +1 . And for every x ∈ V ( T 2 ) and child y of x in T 2 , we have N G ( B y ) ⊆ X ∪ V ( C ) and X ⊆ B 2 z 2 and z 2 ∈ T 2 ↑ y , so N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q ⊆ N G X [ ∪ V ( C )] ( B 2 y ) ∩ ⋃ q ∈ T 2 ↑ y B 2 q . Therefore, every node of T has at most 6 c ( s +1) -heavy children.

̸

̸

̸

̸

Let Y be an arbitrary subset of V ( G ) such that Y has at least max { k +1 , s +1 } common neighbours in G . If Y ∩ V ( C ) = ∅ ̸ = Y -( X ∪ V ( C )) , then X contains all common neighbours of Y , but there are at least s +1 &gt; X | | common neighbours of Y , a contradiction. So either Y ⊆ V ( G ) -V ( C ) or Y ⊆ X ∪ V ( C ) . If Y ⊆ X , then the vertical path in T from z 1 to z ∗ contains all nodes x ∈ V ( T ) with B x ∩ Y = ∅ by the definition of z ∗ . So we may assume Y ⊆ X . Hence, if Y ⊆ V ( G ) -V ( C ) , then all common neighbours of Y in G are contained in V ( G ) -V ( C ) ; if Y ⊆ X ∪ V ( C ) , then all common neighbours of Y in G are contained in V ( C ) ∪ X . Hence there exists a vertical path in T containing all nodes x ∈ V ( T ) with Y ∩ B x = ∅ . This completes the proof.

The value t (and hence c ) in the previous theorem depends on k . We can make it independent of k if drop the 'clean' requirement. The proof is almost identical to the previous theorem, but we rewrite it for completeness.

Theorem 29. Fix s, a, b, ρ ∈ N with a ⩾ 2 and b ⩾ 2 . Let t := ( s +( a -1)( b -1))( a -1)( b -1)+1 . Define c := c s, t, ρ ( ) as in Lemma 10. For any k ∈ N , if G is a graph with tw( G ) ⩽ k -1 and ρ G ( ) ⩽ ρ that contains no 1-extension of K s,a and no skewered K s,b , then for any set S ⊆ V ( G ) with | S | ⩽ s +( a -1)( b -1) , there exists an ( s -1) -quasi-tree-partition ( T, ( B x x ) ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) of G of width at most 18 ck , such that:

- · if z is the root of T then S ⊆ B z , and
- · every node of T has at most 6 c ( s +1) -heavy children.

Proof. We proceed by induction on | V ( G ) | . If G is K s,t -subgraph-free, then the result follows from Theorem 11 (since | S | ⩽ s + ( a -1)( b -1) ⩽ t ⩽ c ⩽ 12 ck ). This proves the base case. Now assume that G contains K s,t . Hence there exists X ⊆ V ( G ) with | X | = s with | N ⩾ s G ( X ) | ⩾ t .

By Lemma 27, every component of G -X contains at most ( a -1)( b -1) vertices in N ⩾ s G ( X ) . So G -X contains at least ⌈ t ( a -1)( b -1) ⌉ ⩾ s + ( a -1)( b -1) + 1 ⩾ | S | + 1 components. Hence there exists a component C of G -X disjoint from S . By induction, G -V ( C ) has an ( s -1) -quasi-tree-partition ( T , 1 ( B 1 x x ) ∈ V ( T 1 ) , ( E 1 v ) v ∈ V ( G ) \ V ( C ) ) of width at most 18 ck , such that if z 1 is the root of T 1 then S ⊆ B 1 z 1 , and every node of T 1 has at most 6 c ( s +1) -heavy children.

Let S ′ := X ∪ ( N ⩾ s G ( X ) ∩ V ( C )) . Note that | S ′ | = | X | + | N ⩾ s G ( X ) ∩ V ( C ) | ⩽ s +( a -1)( b -1) By induction applied to G V [ ( C ) ∪ X ] with specified set S ′ , there exists an ( s -1) -quasi-treepartition ( T , 2 ( B 2 x x ) ∈ V ( T 2 ) , ( E 2 v ) v ∈ V ( C ) ∪ X ) , such that if z 2 is the root of T 2 then S ′ ⊆ B 2 z 2 , and every node of T has at most 6 c ( s +1) -heavy children. Note that E 2 v = ∅ for every v ∈ B 2 z 2 , since z 2 has no parent in T 2 . Similarly, for every child x of z 2 , we may assume E 2 v = ∅ for every v ∈ B 2 x .

Let T 3 be the tree obtained from T 2 by adding a new node z 3 adjacent to z 2 . Consider T 3 to be rooted at z 3 . Let B 3 z 3 := X and B 3 z 2 := B 2 z 2 -X . For each x ∈ V ( T 2 ) -{ z 2 } , let B 3 x := B 2 x . For each x ∈ V ( T 2 ) that is not a child of z 2 and for each v ∈ B 3 x , let E 3 v := E 2 v . For each x ∈ V ( T 2 ) that is a child of z 2 and for every v ∈ B 3 x , let E 3 v be the edges between v and X . By construction, ( B 3 x ) x ∈ V ( T 3 ) is a tree-partition of G X [ ∪ V ( C )] -⋃ v ∈ X V C ∪ ( ) E 3 v . Since N ⩾ s G ( X ) ∩ V ( C ) ⊆ S ′ ⊆ B 2 z 2 , E 3 v is a set of at most s -1 edges of G V [ ( C ) ∪ X ] incident with v for every v ∈ V ( C ) .

̸

Let z ∗ be a node of T 1 with B 1 z ∗ ∩ X = ∅ , and maximising the distance in T 1 between z ∗ and z 1 . Let T be the tree obtained from the disjoint union of T 1 and T 3 by identifying z ∗ and z 3 . Note that T is rooted at z 1 , and the parent of z 3 in T is the parent of z ∗ in T 1 . For each x ∈ V ( T 1 ) , let B x := B 1 x . For each x ∈ V ( T 3 ) -{ z 3 } , let B x := B 3 x . Then ( B x ) x ∈ V ( T ) is a partition of V ( G ) with | B x | ⩽ 18 ck for every x ∈ V ( T ) , and S ⊆ B z 1 .

For each v ∈ V ( G ) -V ( C ) , let E v := E 1 v . For each v ∈ V ( C ) -B 2 z 2 , let E v := E 3 v . By construction, for each v ∈ V ( G ) -( B 2 z 2 \ X ) , E v is a set of at most s -1 edges incident with v , and for each edge vw ∈ E v , if v ∈ B x and w ∈ B y , then by the choice of z ∗ , y ∈ T ↑ x .

̸

For each v ∈ B 2 z 2 -X , let E v be the set of edges between v and X -B 1 z ∗ . Since X ∩ B 1 z ∗ = ∅ , we know | X -B 1 z ∗ | ⩽ | X | -1 ⩽ s -1 , so v ∈ N ⩽ s -1 G ( X -B 1 z ∗ ) for each v ∈ V ( C ) . Hence | E v | ⩽ s -1 for each v ∈ V ( G ) . And by the choice of z ∗ , for every v ∈ B 2 z 2 -X and for each edge vw ∈ E v , if v ∈ B x and w ∈ B y , then y ∈ T ↑ x .

By the definition of E v for v ∈ B 2 z 2 -X , we know ( B x ) x ∈ V ( T ) is a tree-partition of G -⋃ v ∈ V ( G ) E v .

̸

For each x ∈ V ( T 1 ) and child y of x in T 1 , if X ∩ B 1 y = ∅ , then N G ( B y ) = N G ( B 1 y ) ⊆ V ( G ) -V ( C ) , so | N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q | = | N G ( B 1 y ) ∩ ⋃ q ∈ T 1 ↑ y B 1 q | ; if X ∩ B 1 y = ∅ , then by the choice of z ∗ , T ↑ y is disjoint from V ( T 2 ) and hence equal to T 1 ↑ y , so | N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q | = | N G ( B 1 y ) ∩ ⋃ q ∈ T 1 ↑ y B 1 q | . If x ∈ V ( T 1 ) and y is a child of x in T but not in T 1 , then x = z ∗ and y = z 2 , so N G ( B y ) ⊆ X ∪ V ( C ) , and hence N G ( B y ) ∩ ⋃ q ∈ T ↑ y ⊆ X , which has size s &lt; s +1 . And for every x ∈ V ( T 2 ) and child y of x in T 2 , we have N G ( B y ) ⊆ X ∪ V ( C ) and X ⊆ B 2 z 2 and z 2 ∈ T 2 ↑ y , so N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q ⊆ N G X [ ∪ V ( C )] ( B 2 y ) ∩ ⋃ q ∈ T 2 ↑ y B 2 q . Therefore, for every x ∈ V ( T ) , there are at most 6 c children y of x in T such that | N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q | ⩾ s +1 . This completes the proof.

Theorem 29 is applicable with ρ G ( ) ⩽ tw( G ) by (3), in which case c s, t, ρ ( ) ⩽ max { t, t · tw( G ) s -1 +1 } ⩽ t (tw( G ) + 1) s -1 . The next result follows, which implies Corollary 7.

Corollary 30. Fix s, a, b ∈ N with a, b ⩾ 2 . Let t := ( s +( a -1)( b -1))( a -1)( b -1) + 1 . For any k ∈ N , if G is a graph with tw( G ) ⩽ k -1 that contains no 1-extension of K s,a and no skewered K s,b , then G has an ( s -1) -quasi-tree-partition ( T, ( B x x ) ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) of width at most 18 tk s , such that every node has at most 6 tk s -1 ( s +1) -heavy children.

Theorem 29 leads to the following strengthening of Corollary 8 and the known result that graphs with bounded tree-width and maximum degree have bounded tree-partition width (Theorem 1).

Corollary 31. For any a, b.k ∈ N with a, b ⩾ 2 , if G is a graph with tw( G ) ⩽ k -1 that contains no 1-extension of K 1 ,a and no skewered K 1 ,b , then G has a tree-partition ( T, ( B x ) x ∈ V ( T ) ) of width at most 18 a b k 2 2 , such that for every x ∈ V ( T ) , there are at most 6 a b 2 2 children y of x such that | N G ( B y ) ∩ B x | ⩾ 2 .

Proof. By assumption, Theorem 29 is applicable with s = 1 and ρ = k . Let ( T, ( B x x ) ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) be the 0 -quasi-tree-partition of G obtained. Since s = 1 , the width of ( T, ( B x x ) ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) is at most 18 ck , where c ⩽ (1+( a -1)( b -1))( a -1)( b -1)+1 ⩽ (( a -1)( b -1) + 1) 2 ⩽ a b 2 2 . Since ( T, ( B x ) x ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) is a 0 -quasi-tree-partition, E v = ∅ for every v ∈ V ( G ) . Thus ( B x ) x ∈ V ( T ) is a tree-partition of G , and for any x ∈ V ( T ) and child y of x , N G ( B y ) ∩ ⋃ q ∈ T ↑ x B q = N G ( B y ) ∩ B x . Since each node of T has at most 6 c ⩽ 6 a b 2 2 2-heavy children, the final claim follows.

## 6 Colouring II

This section proves colouring results for graphs with no 1-extension of K s,a and no skewered K s,b . The next lemma enables this.

Lemma 32. Fix d, r ∈ N 0 and w ∈ N . If G is a graph that has an r -quasi-tree-partition ( T, ( B x ) x ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) of width at most w such that every node of T has at most d ( r +2) -heavy children, then G is ( r +2) -list-colourable with clustering w d ( +1) w .

Proof. We may add edges to G so that B x is a clique for each x ∈ V ( T ) , and for each edge xy of E T ( ) , if y is an ( r +2) -heavy child of x , then every vertex in B x is adjacent in G to every vertex in B y .

Let ⩽ T be a BFS-ordering of V ( T ) . Let ⩽ G be a linear ordering of V ( G ) such that for any distinct x, y ∈ V ( T ) with x ⩽ T y , if u ∈ B x and v ∈ B y , then u ⩽ G v . For any S ⊆ V ( G ) , let m S ( ) be the smallest vertex in S according to ⩽ G . For each subgraph H of G , let m(H) := m V H ( ( )) . For any S , S 1 2 , where each S i is a subset of V ( G ) or a subgraph of G , we define S 1 ⩽ G S 2 if and only if m S ( 1 ) ⩽ G m S ( 2 ) . Denote V ( T ) by { t 1 , t 2 , . . . , t | V ( T ) | } such that t i ⩽ T t j for every i ⩽ j .

Let L be an arbitrary ( r +2) -list-assignment of G .

Define f 1 to be an L | B t 1 -colouring of G B [ t 1 ] by defining f 1 ( v ) to be an arbitrary element in L v ( ) for every v ∈ B t 1 . For every i ∈ | [ V ( T ) ] | -{ } 1 , define an L | ⋃ i j =1 B t j -colouring f i of G [ ⋃ i j =1 B t j ] as follows:

- · Let M i be the f i -1 -monochromatic component intersecting B p i with the smallest m M ( i ) .
- · For each v ∈ ⋃ i -1 j =1 B t j , let f i ( v ) := f i -1 ( v ) . · Let p i be the parent of t i in T .
- · Let a i be the colour of M i .
- · If | N G ( B t i ) ∩ ⋃ q ∈ T ↑ t i B q | ⩾ r + 2 , then for every v ∈ B t i , let f i ( v ) be an element in L v ( ) -{ a , f i i -1 ( u ) : uv ∈ E v } .

- · If | N G ( B t i ) ∩ ⋃ q ∈ T ↑ t i B q | ⩽ r + 1 , then for every v ∈ B t i , let f i ( v ) be an element in L v ( ) -{ f i -1 ( u ) : u ∈ N G ( B t i ) ∩ ⋃ q ∈ T ↑ t i B q } . Since | L v ( ) | ⩾ r +2 , f i ( v ) can be defined as above.

Let f = f | V ( T ) | . It suffices to show that f has clustering c := w d ( +1) w .

̸

Claim 32.1. If uv is an edge of G with { u, v } ⊆ V ( M ) and u ⩽ G v , then there exists an edge xy of T such that { u, v } ⊆ B x ∪ B y .

Let M be an arbitrary f -monochromatic component. Let S M = { t ∈ V ( T ) : B t ∩ V ( M ) = ∅} . To prove | V ( M ) | ⩽ c , it suffices to show that S M induces a subtree T M with maximum degree at most d +1 (Claim 32.3 below) such that every path in T M from the root of T M to any other vertex contains at most w vertices (implied by Claim 32.5 below). This will imply that | V ( M ) | ⩽ w S | M | ⩽ w ∑ w -1 i =0 ( d +1) i ⩽ w d ( +1) w = c , as desired.

̸

̸

̸

Proof. Let x, y ∈ V ( T ) such that u ∈ B x and v ∈ B y . Since u ⩽ G v , x ⩽ T y . Suppose to the contrary that x = y and x is not the parent of y . Since ( B t : t ∈ V ( T )) is a treepartition of G -⋃ q ∈ V ( G ) E q , uv ∈ E u ∪ E v . By the property of E u and E v , we know that uv ∈ E v and x ∈ T ↑ y . Note that x ∈ T ↑ y implies that u ∈ N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q . If | N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q | ⩾ r + 2 , then since uv ∈ E v , f ( u ) = f ( v ) by the definition of f . If | N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q | ⩽ r + 1 , then since u ∈ N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q , f ( u ) = f ( v ) by the definition of f . Hence f ( u ) = f ( v ) in either case, contradicting that M is monochromatic.

Since M is connected, by Claim 32.1, we know T M = T S [ M ] is a subtree of T .

Claim 32.2. For every edge ty of T M , where t is the parent of y , | N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q | ⩾ r +2 .

̸

Proof. Since { t, y } ⊆ S M , there exist u ∈ B t ∩ V ( M ) and v ∈ B y ∩ V ( M ) . Since M is connected, there exists a path P in M between u and v . We choose u and v such that P can be chosen to be as short as possible. By Claim 32.1, uv ∈ E G ( ) . Since t ∈ T ↑ y , u ∈ N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q . So if | N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q | ⩽ r +1 , then f ( u ) = f ( v ) , a contradiction. Claim 32.3. T M has maximum degree at most d +1 .

Proof. Suppose to the contrary that there exists t ∈ V ( T M ) with degree at least d +2 . So t has at least d +1 children in T M . By the property of ( B x x ) ∈ V ( T ) , there exists a child y of t in T M such that | N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q | ⩽ r +1 , contradicting Claim 32.2.

Claim 32.4. For every vertical path P in T M , there exists a path P M in M such that | V ( P M ) ∩ B t | = 1 for every t ∈ V ( P ) , and V ( P M ) ∩ B t = ∅ for every t ∈ V ( T ) -V ( P ) .

Proof. By Claim 32.2, for every edge ty of P , where t is a parent of y , | N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q | ⩾ r +2 , so B t ∪ B y is a clique of G by assumption. Then the claim follows.

̸

Claim 32.5. For any k ∈ N , if there exists a vertical path P in T M on at least k vertices, then there exist at least k -1 f -monochromatic components Q with m Q ( ) &lt; G m M ( ) and V ( Q ) ∩ B t P = ∅ , where t P is the root of P .

̸

Proof. We prove this claim by induction on k . The case k = 1 is obvious. So we may assume k ⩾ 2 .

By Claim 32.4, there exists a path P M in M such that | V ( P M ) ∩ B t | = 1 for every t ∈ V ( P ) , and V ( P M ) ∩ B t = ∅ for every t ∈ V ( T ) -V ( P ) . Let y be the end of P other than t P ( y exists since k ⩾ 2 ). Let v P be the vertex in V ( P M ) ∩ B y . Let p be the parent of y . Let i ∈ | [ V ( T ) ] | such that y = t i . Note that there exists a f i -1 -monochromatic component M ′ containing P M -v P . Since M ′ ⊆ M m M , ( ) ⩽ G m M ( ′ ) . By considering the path in T M from the root of T M to p , we know m M ( ) = m M ( ′ ) by Claims 32.2 and 32.4.

̸

̸

By Claim 32.2, | N G ( B y ) ∩ ⋃ q ∈ T ↑ y B q | ⩾ r +2 . Since V ( M ) ∩ B y = ∅ , a i is not the colour of M . That is, there exists a f i -1 -monochromatic component C i intersecting B p with m C ( i ) &lt; G m M ( ′ ) = m M ( ) . Let C be the f -monochromatic component containing C i . So m C ( ) ⩽ G m C ( i ) &lt; G m M ( ) . Applying Claims 32.1, 32.2 and 32.4 to C , we know m C ( ) = m C ( i ) , and the root r C of the subtree T C induced by { t ∈ V ( T ) : B t ∩ V ( C ) = ∅} is an ancestor of the root r M of T M or equal to r M . Hence there exists a vertical path in T C from t P to p on at least k -1 vertices, and V ( C ) ∩ B t P = ∅ . By the induction hypothesis, there exist at least k -2 f -monochromatic components Q with m Q ( ) &lt; G m C ( ) and V ( Q ) ∩ B t P = ∅ . By collecting those Q together with C , we obtain at least k -1 f -monochromatic components Q with m Q &lt; ( ) G m M ( ) and V ( Q ) ∩ B t P = ∅ .

̸

̸

̸

Let r M be the root of T M . Since | B x | ⩽ w for every x ∈ V ( T ) , there are at most w -1 f -monochromatic components Q with m Q &lt; ( ) G m M ( ) and V ( Q ) ∩ B r M = ∅ . By Claim 32.5, every vertical path in T M contains at most w vertices. This completes the proof.

If the tree of the tree-partition has bounded maximum degree, then we can do fractional colouring that reduces the ratio for the number of colours. The proof is very similar, but we write it again for completeness.

Lemma 33. For any integers w,ℓ ⩾ 1 and d, r ⩾ 0 , if a graph G has an r -quasi-tree-partition ( T, ( B x x ) ∈ V ( T ) , ( E v ) v ∈ V ( G ) ) of width at most w and degree at most d , then G is (( r +1) +1) ℓ : ℓ -list-colourable with clustering wd w .

Proof. We may add edges to G so that B x is a clique for every x ∈ V ( T ) , and for any edge xy of E T ( ) , every vertex in B x is adjacent in G to every vertex in B y .

Let ⩽ T be a BFS-ordering of V ( T ) . Let ⩽ G be a linear ordering of V ( G ) such that for any distinct x, y ∈ V ( T ) with x ⩽ T y , if u ∈ B x and v ∈ B y , then u ⩽ G v . For any S ⊆ V ( G ) , let m S ( ) be the smallest vertex in S according to ⩽ G . For any subgraph H of G , let m H ( ) = m V H ( ( )) . For any S , S 1 2 , where each S i is a subset of V ( G ) or a subgraph of G , we define S 1 ⩽ G S 2 if and only if m S ( 1 ) ⩽ G m S ( 2 ) . Denote V ( T ) by { t 1 , t 2 , ..., t | V ( T ) | } such that t i ⩽ T t j for every i ⩽ j .

Let L be an arbitrary (( r +1) ℓ +1) -list-assignment of G .

Define f 1 to be an L | B t 1 -colouring of G B [ t 1 ] by defining f 1 ( v ) to be an arbitrary subset of L v ( ) with size ℓ for every v ∈ B t 1 . For every i ∈ | [ V ( T ) ] | -{ } 1 , we define an L | ⋃ i j =1 B t j -colouring f i of G [ ⋃ i j =1 B t j ] as follows:

̸

- · For each v ∈ ⋃ i -1 j =1 B t j , let f i ( v ) := f i -1 ( v ) . · Let p i be the parent of t i in T .
- · Let M i be the f i -1 -monochromatic component intersecting B p i with the smallest m M ( i ) .
- · Let a i be the colour of M i .
- · For each v ∈ B t i , let f i ( v ) be a subset of L v ( ) - { ( a i } ∪ ⋃ uv ∈ E v f i -1 ( u )) with size ℓ . Since | E v | ⩽ r and | L v ( ) | ⩾ ( r +1) ℓ +1 , f i ( v ) can be defined as above.

Let f = f | V ( T ) | . It suffices to show that f has clustering c := wd w .

̸

Claim 33.1. If uv is an edge of G with { u, v } ⊆ V ( M ) and u ⩽ G v , then there exists an edge xy of T such that { u, v } ⊆ B x ∪ B y .

Let M be an arbitrary f -monochromatic component. Let S M = { t ∈ V ( T ) : B t ∩ V ( M ) = ∅} . To prove | V ( M ) | ⩽ c , it suffices to show that S M induces a subtree T M such that every path in T M from the root of T M to any other vertex contains at most w vertices (since it implies that | V ( M ) | ⩽ w S | M | ⩽ w ∑ w -1 i =0 d i ⩽ wd w = c , as ∆( T ) ⩽ d ).

̸

̸

Proof. Let x, y ∈ V ( T ) such that u ∈ B x and v ∈ B y . Since u ⩽ G v , x ⩽ T y . Suppose to the contrary that x = y and x is not the parent of y . Since ( B t : t ∈ V ( T )) is a tree-partition of G -⋃ q ∈ V ( G ) E q , uv ∈ E u ∪ E v . By the property of E u and E v , we know that uv ∈ E v and x ∈ T ↑ y . Since uv ∈ E v , f ( u ) = f ( v ) by the definition of f , contradicting that M is monochromatic.

Since M is connected, by Claim 33.1, we know T M = T S [ M ] is a subtree of T .

Claim 33.2. For every vertical path P in T M , there exists a path P M in M such that | V ( P M ) ∩ B t | = 1 for every t ∈ V ( P ) , and V ( P M ) ∩ B t = ∅ for every t ∈ V ( T ) -V ( P ) .

Proof. Since for every edge ty of P , B t ∪ B y is a clique of G by assumption, the claim follows.

̸

Claim 33.3. For any k ∈ N , if there exists a vertical path P in T M on at least k vertices, then there exist at least k -1 f -monochromatic components Q with m Q ( ) &lt; G m M ( ) and V ( Q ) ∩ B t P = ∅ , where t P is the root of P .

Proof. We prove this claim by induction on k . The case k = 1 is obvious. So we may assume k ⩾ 2 .

By Claim 33.2, there exists a path P M in M such that | V ( P M ) ∩ B t | = 1 for every t ∈ V ( P ) , and V ( P M ) ∩ B t = ∅ for every t ∈ V ( T ) -V ( P ) . Let y be the end of P other than t P ( y exists since k ⩾ 2 ). Let v P be the vertex in V ( P M ) ∩ B y . Let p be the parent of y . Let i ∈ | [ V ( T ) ] | such that y = t i . Note that there exists a f i -1 -monochromatic component M ′ containing P M -v P . Since M ′ ⊆ M m M , ( ) ⩽ G m M ( ′ ) . By considering the path in T M from the root of T M to p , we know m M ( ) = m M ( ′ ) .

̸

Since V ( M ) ∩ B y = ∅ , a i is not the colour of M . That is, there exists a f i -1 -monochromatic component C i intersecting B p with m C ( i ) &lt; G m M ( ′ ) = m M ( ) . Let C be the f -monochromatic component containing C i . So m C ( ) ⩽ G m C ( i ) &lt; G m M ( ) . Applying Claim 33.1 and Claim 33.2

̸

̸

̸

to C , we know m C ( ) = m C ( i ) , and the root r C of the subtree T C induced by { t ∈ V ( T ) : B t ∩ V ( C ) = ∅} is an ancestor of the root r M of T M or equal to r M . Hence there exists a vertical path in T C from t P to p on at least k -1 vertices, and V ( C ) ∩ B t P = ∅ . By the induction hypothesis, there exist at least k -2 f -monochromatic components Q with m Q ( ) &lt; G m C ( ) and V ( Q ) ∩ B t P = ∅ . By collecting those Q together with C , we obtain at least k -1 f -monochromatic components Q with m Q &lt; ( ) G m M ( ) and V ( Q ) ∩ B t P = ∅ .

̸

Let r M be the root of T M . Since | B x | ⩽ w for every x ∈ V ( T ) , there are at most w -1 f -monochromatic components Q with m Q &lt; ( ) G m M ( ) and V ( Q ) ∩ B r M = ∅ . By Claim 33.3, every vertical path in T M contains at most w vertices. This proves the lemma.

Theorem 34. For any s, a, b, k ∈ N with a, b ⩾ 2 , there exists c ∈ N such that for any ℓ ∈ N and graph G with tw( G ) ⩽ k -1 :

- 1. If G contains no 1-extension of K s,a and no skewered K s,b , then G is ( s +1) -list-colourable with clustering c .
- 2. If G is K s,a -subgraph-free, then G is ( sℓ +1) : ℓ -list-colourable with clustering c .

Proof. Recall that ρ G ( ) ⩽ tw( G ) by (3). Statement 1 follows from Theorem 29 and Lemma 32. Statement 2 follows from Lemma 12 and Lemma 33.

Acknowledgement: This paper was partially written when the first author visited the National Center for Theoretical Sciences in Taiwan. He thanks the National Center for Theoretical Sciences for its hospitality.

## References

- [1] Noga Alon, Guoli Ding, Bogdan Oporowski, and Dirk Vertigan . Partitioning into graphs with only small components. J. Combin. Theory Ser. B , 87(2):231-243, 2003.
- [2] Noga Alon, Paul Seymour, and Robin Thomas . Planar separators. SIAM J. Discrete Math. , 7(2):184-193, 1994.
- [3] János Barát and David R. Wood . Notes on nonrepetitive graph colouring. Electron. J. Combin. , 15:R99, 2008.
- [4] Hans L. Bodlaender . The complexity of finding uniform emulations on fixed graphs. Inform. Process. Lett. , 29(3):137-141, 1988.
- [5] Hans L. Bodlaender . The complexity of finding uniform emulations on paths and ring networks. Inform. and Comput. , 86(1):87-106, 1990.
- [6] Hans L. Bodlaender . A partial k -arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. , 209(1-2):1-45, 1998.
- [7] Hans L. Bodlaender . A note on domino treewidth. Discrete Math. Theor. Comput. Sci. , 3(4):141-150, 1999.
- [8] Hans L. Bodlaender and Joost Engelfriet . Domino treewidth. J. Algorithms , 24(1):94-123, 1997.
- [9] Hans L. Bodlaender, Carla Groenland, and Hugo Jacob . On the parameterized complexity of computing tree-partitions. In Holger Dell and Jesper Nederlof , eds., Proc. 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), vol. 249 of LIPIcs , pp. 7:1-7:20. Schloss Dagstuhl, 2022.

̸

- [10] Hans L. Bodlaender and Jan van Leeuwen . Simulation of large networks on smaller networks. Inform. and Control , 71(3):143-180, 1986.
- [11] Rutger Campbell, Katie Clinch, Marc Distel, J. Pascal Gollin, Kevin Hendrey, Robert Hickingbotham, Tony Huynh, Freddie Illingworth, Youri Tamitegama, Jane Tan, and David R. Wood . Product structure of graph classes with bounded treewidth. Combin. Probab. Comput. , 33(3):351-376, 2024.
- [12] Rutger Campbell, Marc Distel, J. Pascal Gollin, Daniel J. Harvey, Kevin Hendrey, Robert Hickingbotham, Bojan Mohar, and David R. Wood . Graphs of linear growth have bounded treewidth. Electron. J. Combin. , 30:#3.1, 2023.
- [13] Paz Carmi, Vida Dujmović, Pat Morin, and David R. Wood . Distinct distances in graph drawings. Electron. J. Combin. , 15:R107, 2008.
- [14] Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, and Dimitrios M. Thilikos . An O(log OPT)-approximation for covering and packing minor models of θ r . Algorithmica , 80(4):1330-1356, 2018.
- [15] Ilkyoo Choi and Louis Esperet . Improper coloring of graphs on surfaces. J. Graph Theory , 91(1):16-34, 2019.
- [16] Ilkyoo Choi, Chun-Hung Liu, and Sang-il Oum . Characterization of cycle obstruction sets for improper coloring planar graphs. SIAM J. Discret. Math. , 32(2):1209-1228, 2018.
- [17] Joshua Crouch and Chun-Hung Liu . Weak diameter choosability of graphs with an excluded minor. 2023, arXiv:2310.17795.
- [18] Emilio Di Giacomo, Giuseppe Liotta, and Henk Meijer . Computing straight-line 3D grid drawings of graphs in linear volume. Comput. Geom. Theory Appl. , 32(1):26-58, 2005.
- [19] Guoli Ding and Bogdan Oporowski . Some results on tree decomposition of graphs. J. Graph Theory , 20(4):481-499, 1995.
- [20] Guoli Ding and Bogdan Oporowski . On tree-partitions of graphs. Discrete Math. , 149(13):45-58, 1996.
- [21] Marc Distel and David R. Wood . Tree-partitions with small bounded degree trees. 2022, arXiv:2210.12577.
- [22] Marc Distel and David R. Wood . Tree-partitions with bounded degree trees. In David R. Wood, Jan de Gier, and Cheryl E. Praeger , eds., 2021-2022 MATRIX Annals , pp. 203-212. Springer, 2024.
- [23] Nemanja Draganić, Marc Kaufmann, David Munhá Correia, Kalina Petrova, and Raphael Steiner . Size-Ramsey numbers of structurally sparse graphs. 2023, arXiv:2307.12028.
- [24] Vida Dujmović, David Eppstein, and David R. Wood . Structure of graphs with locally restricted crossings. SIAM J. Discrete Math. , 31(2):805-824, 2017.
- [25] Vida Dujmović, Louis Esperet, Pat Morin, Bartosz Walczak, and David R. Wood . Clustered 3-colouring graphs of bounded degree. Combin. Probab. Comput. , 31(1):123-135, 2022.
- [26] Vida Dujmović, Louis Esperet, Pat Morin, and David R. Wood . Proof of the clustered Hadwiger conjecture. In Proc. 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS '23), pp. 1921-1930. 2023. arXiv:2306.06224.
- [27] Vida Dujmović, Pat Morin, and David R. Wood . Layout of graphs with bounded tree-width. SIAM J. Comput. , 34(3):553-579, 2005.
- [28] Vida Dujmović, Pat Morin, and David R. Wood . Layered separators in minor-closed graph classes with applications. J. Combin. Theory Ser. B , 127:111-147, 2017.
- [29] Vida Dujmović, Matthew Suderman, and David R. Wood . Graph drawings with few slopes. Comput. Geom. Theory Appl. , 38:181-193, 2007.
- [30] Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, and David R. Wood . Bounded-degree planar graphs do not have bounded-degree product structure. 2024.
- [31] Zdeněk Dvořák . Sublinear separators, fragility and subexponential expansion. European J. Combin. , 52(A):103-119, 2016.
- [32] Zdeněk Dvořák and Sergey Norin . Strongly sublinear separators and polynomial expansion. SIAM J. Discrete Math. , 30(2):1095-1101, 2016.

- [33] Zdeněk Dvořák and Sergey Norin . Islands in minor-closed classes. I. Bounded treewidth and separators. 2017, arXiv:1710.02727.
- [34] Zdeněk Dvořák and Jean-Sébastien Sereni . On fractional fragility rates of graph classes. Electronic J. Combinatorics , 27:P4.9, 2020.
- [35] Anders Edenbrandt . Quotient tree partitioning of undirected graphs. BIT , 26(2):148-155, 1986.
- [36] Katherine Edwards, Dong Yeap Kang, Jaehoon Kim, Sang-il Oum, and Paul Seymour . A relative of Hadwiger's conjecture. SIAM J. Discrete Math. , 29(4):2385-2388, 2015.
- [37] Louis Esperet and Gwenaël Joret . Colouring planar graphs with three colours and no large monochromatic components. Combin., Probab. Comput. , 23(4):551-570, 2014.
- [38] Louis Esperet and Pascal Ochem . Islands in graphs on surfaces. SIAM J. Discrete Math. , 30(1):206-219, 2016.
- [39] Louis Esperet and Jean-Florent Raymond . Polynomial expansion and sublinear separators. European J. Combin. , 69:49-53, 2018.
- [40] Louis Esperet and David R. Wood . Colouring strong products. European J. Combin. , 121:103847, 2024.
- [41] Zuzana Farkasová and Roman Soták . Fractional and circular 1-defective colorings of outerplanar graphs. Australas. J. Combin. , 63:1-11, 2015.
- [42] John P. Fishburn and Raphael A. Finkel . Quotient networks. IEEE Trans. Comput. , C-31(4):288-295, 1982.
- [43] Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dimitrios M. Thilikos . Packing and covering immersion models of planar subcubic graphs. In Pinar Heggernes , ed., Proc. 42nd Int'l Workshop on Graph-Theoretic Concepts in Computer Science (WG 2016), vol. 9941 of Lecture Notes in Comput. Sci. , pp. 74-84. 2016.
- [44] John R. Gilbert, Joan P. Hutchinson, and Robert E. Tarjan . A separator theorem for graphs of bounded genus. J. Algorithms , 5(3):391-407, 1984.
- [45] Wayne Goddard and Honghai Xu . Fractional, circular, and defective coloring of series-parallel graphs. J. Graph Theory , 81(2):146-153, 2016.
- [46] Rudolf Halin . Tree-partitions of infinite graphs. Discrete Math. , 97:203-217, 1991.
- [47] Daniel J. Harvey and David R. Wood . Parameters tied to treewidth. J. Graph Theory , 84(4):364-385, 2017.
- [48] Kevin Hendrey and David R. Wood . Defective and clustered colouring of sparse graphs. Combin. Probab. Comput. , 28(5):791-810, 2019.
- [49] Tony Huynh and David R. Wood . Tree densities of sparse graph classes. Canadian J. Math. , 74(5):1385-1404, 2022.
- [50] Nina Kamcev, Anita Liebenau, David R. Wood, and Liana Yepremyan . The size Ramsey number of graphs with bounded treewidth. SIAM J. Discrete Math. , 35(1):281-293, 2021.
- [51] Dong Yeap Kang and Sang-il Oum . Improper coloring of graphs with no odd clique minor. Combin. Probab. Comput. , 28(5):740-754, 2019.
- [52] Ken-ichi Kawarabayashi and Bojan Mohar . A relaxed Hadwiger's conjecture for list colorings. J. Combin. Theory Ser. B , 97(4):647-651, 2007.
- [53] William Klostermeyer . Defective circular coloring. Australas. J. Combin. , 26:21-32, 2002.
- [54] Alexandr V. Kostochka . The minimum Hadwiger number for graphs with a given mean degree of vertices. Metody Diskret. Analiz. , 38:37-58, 1982.
- [55] Alexandr V. Kostochka . Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica , 4(4):307-316, 1984.
- [56] Dietrich Kuske and Markus Lohrey . Logical aspects of Cayley-graphs: the group case. Ann. Pure Appl. Logic , 131(1-3):263-286, 2005.
- [57] Chun-Hung Liu . Immersion and clustered coloring. J. Combin. Theory Ser. B , 158:252-282, 2023.
- [58] Chun-Hung Liu . Defective coloring is perfect for minors. Combinatorica , 44:467-507, 2024.
- [59] Chun-Hung Liu and Sang-il Oum . Partitioning H -minor free graphs into three subgraphs with no large components. J. Combin. Theory Ser. B , 128:114-133, 2018.

- [60] Chun-Hung Liu and David R. Wood . Clustered coloring of graphs excluding a subgraph and a minor. 2019, arXiv:1905.09495.
- [61] Chun-Hung Liu and David R. Wood . Clustered graph coloring and layered treewidth. 2019, arXiv:1905.08969.
- [62] Chun-Hung Liu and David R. Wood . Clustered variants of Hajós' conjecture. J. Combin. Theory Ser. B , 152:27-54, 2022.
- [63] Chun-Hung Liu and David R. Wood . Clustered coloring of graphs with bounded layered treewidth and bounded degree. European J. Combin. , p. 103730, 2023.
- [64] Peter Mihók, Janka Oravcová, and Roman Soták . Generalized circular colouring of graphs. Discuss. Math. Graph Theory , 31(2):345-356, 2011.
- [65] Bojan Mohar, Bruce Reed, and David R. Wood . Colourings with bounded monochromatic components in graphs of given circumference. Australas. J. Combin. , 69(2):236-242, 2017.
- [66] Sergey Norin, Alex Scott, Paul Seymour, and David R. Wood . Clustered colouring in minor-closed classes. Combinatorica , 39(6):1387-1412, 2019.
- [67] Sergey Norin, Alex Scott, and David R. Wood . Clustered colouring of graph classes with bounded treedepth or pathwidth. Combin. Probab. Comput. , 32:122-133, 2023.
- [68] Serguei Norine, Paul Seymour, Robin Thomas, and Paul Wollan . Proper minor-closed families are small. J. Combin. Theory Ser. B , 96(5):754-757, 2006.
- [69] Patrice Ossona de Mendez, Sang-il Oum, and David R. Wood . Defective colouring of graphs excluding a subgraph or minor. Combinatorica , 39(2):377-410, 2019.
- [70] Jean-Florent Raymond and Dimitrios M. Thilikos . Recent techniques and results on the Erdős-Pósa property. Discrete Appl. Math. , 231:25-43, 2017.
- [71] Bruce A. Reed . Tree width and tangles: a new connectivity measure and some applications. In R. A. Bailey , ed., Surveys in combinatorics , vol. 241 of London Math. Soc. Lecture Note Ser. , pp. 87-162. Cambridge Univ. Press, 1997.
- [72] Neil Robertson and Paul Seymour . Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms , 7(3):309-322, 1986.
- [73] Edward R. Scheinerman and Daniel H. Ullman . Fractional graph theory. Wiley, 1997.
- [74] Detlef Seese . Tree-partite graphs and the complexity of algorithms. In Lothar Budach , ed., Proc. Int'l Conf. on Fundamentals of Computation Theory , vol. 199 of Lecture Notes Comput. Sci. , pp. 412-421. Springer, 1985.
- [75] Andrew Thomason . An extremal function for contractions of graphs. Math. Proc. Cambridge Philos. Soc. , 95(2):261-265, 1984.
- [76] Andrew Thomason . Complete minors in pseudorandom graphs. Random Structures Algorithms , 17(1):26-28, 2000.
- [77] Jan van den Heuvel and David R. Wood . Improper colourings inspired by Hadwiger's conjecture. J. London Math. Soc. , 98:129-148, 2018. arXiv:1704.06536.
- [78] David R. Wood . Vertex partitions of chordal graphs. J. Graph Theory , 53(2):167-172, 2006.
- [79] David R. Wood . On the maximum number of cliques in a graph. Graphs Combin. , 23(3):337-352, 2007.
- [80] David R. Wood . On tree-partition-width. European J. Combin. , 30(5):1245-1253, 2009.
- [81] David R. Wood . Contractibility and the Hadwiger conjecture. European J. Combin. , 31(8):21022109, 2010.
- [82] David R. Wood . Defective and clustered graph colouring. Electron. J. Combin. , DS23, 2018. Version 1.
- [83] David R. Wood and Jan Arne Telle . Planar decompositions and the crossing number of graphs with an excluded minor. New York J. Math. , 13:117-146, 2007.
- [84] Rui-Ray Zhang and Massih-Reza Amini . Generalization bounds for learning under graphdependence: A survey. 2022, arXiv:2203.13534.
Chun-Hung Liu David R. Wood
Quasi-tree-partitions of graphs with an excluded subgraph
This paper studies the structure of graphs with given tree-width and
excluding a fixed complete bipartite subgraph, which generalises the bounded
degree setting. We give a new structural description of such graphs in terms of
so-called quasi-tree-partitions. We demonstrate the utility of this result
through applications to (fractional) clustered colouring. Further
generalisations of these structural and colouring results are presented.