---
abstract: 'Treewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This paper describes several graph parameters tied to treewidth, including separation number, tangle number, well-linked number and cartesian tree product number. We prove that these parameters are tied to treewidth. In a number of cases we also improve known bounds, provide simpler proofs and show that the inequalities presented are tight.'
address:
- 'Department of Mathematics and Statistics The University of Melbourne Melbourne, Australia'
- 'School of Mathematical Sciences Monash University Melbourne, Australia'
author:
- 'Daniel J. Harvey'
- 'David R. Wood'
bibliography:
- 'myBibliography.bib'
- 'extra.bib'
title: Parameters Tied to Treewidth
---

[^1] [^2]

Introduction
============

Treewidth is an important graph parameter for two key reasons. Firstly, treewidth has many algorithmic applications; for example, there are many results showing that NP-Hard problems can be solved in polynomial time on classes of graphs with bounded treewidth (see @Bodlaender-AC93 for a survey). Treewidth is inherently related to graph separators, which are “small" sets of vertices whose removal leaves no component with more than half the vertices (or thereabouts). Separators are particularly useful when using dynamic programming to solve graph problems; find and delete a separator, recursively solve the problem on the remaining components, and then combine these solutions to obtain a solution for the original problem.

Secondly, treewidth is a key parameter in graph structure theory, especially in Robertson and Seymour’s seminal series of papers on graph minors [@RS-GraphMinors]. Ultimately, the purpose of these papers was to prove what it now known as the Graph Minor Theorem (often referred to as Wagner’s Conjecture), which states that any class of minor-closed graphs (other than the class of all graphs) has a finite set of forbidden minors. In order to prove this, Robertson and Seymour separately considered classes with bounded treewidth and classes with unbounded treewidth. The Graph Minor Theorem is (comparatively) easy to prove for classes with bounded treewidth [@RS-GraphMinorsIV-JCTB90]. In order to prove the Graph Minor Theorem for classes with unbounded treewidth, Robertson and Seymour showed that graphs with large treewidth contain large grid minors. This Grid Minor Theorem has been reproved by many researchers; we will discuss it more thoroughly in Section \[section:gridminors\]. In proving these results, the parameters *linkedness* and *well-linked number* were used. At the heart of the Graph Minor Theorem is the Graph Minor Structure Theorem, which describes how to construct a graph in a minor-closed class; see @KM-GC07 for a survey of several versions of the Graph Minor Structure Theorem. The most complex version, and the one used in the proof of the Graph Minor Theorem, describes the structure of graphs in a minor-closed class with unbounded treewidth in terms of *tangles*. Robertson and Seymour combined all these ingredients in their proof of the Graph Minor Theorem. The purpose of this paper is to present a number of known graph parameters that are closely related to treewidth, including those mentioned above such as separation number, linkedness, well-linked number and tangle number.

Formally, a *graph parameter* is a real-valued function $\alpha$ defined on all graphs such that $\alpha(G_1)=\alpha(G_2)$ whenever $G_1$ and $G_2$ are isomorphic. Two graph parameters $\alpha(G)$ and $\beta(G)$ are *tied*[^3] if there exists a function $f$ such that for every graph $G$, $$\alpha(G) \leq f(\beta(G)) \text{ and } \beta(G) \leq f(\alpha(G)).$$ Moreover, say that $\alpha$ and $\beta$ are *polynomially tied* if $f$ is a polynomial.

Drawing on results in the literature, we prove the following:

\[theorem:pttt\] The following graph parameters are polynomially tied:

-   treewidth,

-   bramble number,

-   minimum integer $k$ such that $G$ is a spanning subgraph of a $k$-tree,

-   minimum integer $k$ such that $G$ is a spanning subgraph of a chordal graph with no $(k+2)$-clique,

-   separation number,

-   branchwidth,

-   tangle number,

-   lexicographic tree product number,

-   cartesian tree product number,

-   linkedness,

-   well-linked number,

-   maximum order of a grid minor,

-   maximum order of a grid-like-minor,

-   Hadwiger number of the Cartesian product $G\square K_2$ (viewed as a function of $G$),

-   fractional Hadwiger number,

-   $r$-integral Hadwiger number for each $r\geq 2$.

@Fox11 states (without proof) a theorem similar to Theorem \[theorem:pttt\] with the parameters treewidth, bramble number, separation number, maximum order of a grid minor, fractional Hadwiger number, and $r$-integral Hadwiger number for each $r\geq 2$. Indeed, this statement of Fox motivated the present paper.

This paper investigates the parameters in Theorem \[theorem:pttt\], showing where these parameters have been useful, and provides proofs that each parameter is tied to treewidth (except in a few cases). In a number of cases we improve known bounds, provide simpler proofs and show that the inequalities presented are tight. The following graph is a key example. Say $n,k$ are integers. Let $\psi_{n,k}$ be the graph with vertex set $A \cup B$, where $A$ is a clique on $n$ vertices, $B$ is an independent set on $kn$ vertices, and $A \cap B = \emptyset$, such that each vertex of $A$ is adjacent to exactly $k(n-1)$ vertices of $B$ and each vertex of $B$ is adjacent to exactly $n-1$ vertices of $A$. (Note it always possible to add edges in this fashion; pair up each vertex in $A$ with $k$ vertices in $B$ such that all pairs are disjoint, and then add all edges from $A$ to $B$ except those between paired vertices.)

![The graph $\psi_{4,2}$.](psi_graph)

Treewidth and Basics
====================

Let $G$ be a graph. A *tree decomposition* of $G$ is a pair $(T, (B_x \subseteq V(G))_{x \in V(T)})$ consisting of

-   a tree $T$,

-   a collection of *bags* $B_x$ containing vertices of $G$, indexed by the nodes of $T$.

The following conditions must also hold:

-   For all $v \in V(G)$, the set $\{ x \in V(T) : v \in B_x\}$ induces a non-empty subtree of $T$.

-   For all $vw \in E(G)$, there is some bag $B_x$ containing both $v$ and $w$.

The *width* of a tree decomposition is defined as the size of the largest bag minus 1. The treewidth ${\textsf{\textup{tw}}}(G)$ is the minimum width over all tree decompositions of $G$. Often, for the sake of simplicity, we will refer to a tree decomposition simply as $T$, leaving the set of bags implied whenever this is unambiguous. For similar reasons, often we say that bags $X$ and $Y$ are adjacent (or we refer to an edge $XY$), instead of the more accurate statement that the nodes of $T$ indexing $X$ and $Y$ are adjacent.

Treewidth was defined by @Halin76 (in an equivalent form which Halin called $S$-functions) and independently by @RS-GraphMinorsII-JAlg86. Intuitively, a graph with low treewidth is simple and treelike — note that a tree itself has treewidth 1. (In fact, ensuring this fact is the reason that 1 was subtracted in the definition of width.) On the other hand, a complete graph $K_{n}$ has treewidth $n-1$.

Say a tree decomposition is *normalised* if each bag has the same size, and if $|X-Y|=|Y-X|=1$ whenever $XY$ is an edge.

\[lemma:normal\] If $G$ has a tree decomposition of width $k$, then $G$ has a normalised tree decomposition of width $k$.

Let $T$ be the tree decomposition of $G$ with width $k$. Thus $T$ contains a bag of size $k+1$. If some bag of $T$ does not contain $k+1$ vertices, then as $T$ is connected, there exist adjacent bags $X$ and $Y$ such that $|X|=k+1$ and $|Y|<k+1$. Then $X-Y$ is non-empty; take some vertex of $X-Y$ and add it to $Y$. This increases $|Y|$, so repeat this process until all bags have size $k+1$.

Now, consider an edge $XY$. Since $|X|=|Y|$, it follows $|X-Y|=|Y-X|$. If $|X-Y| > 1$, then let $v \in X-Y$ and $u \in Y-X$. Subdivide the edge $XY$ of $T$ and call the new bag $Z$. Let $Z = X - \{v\} + \{u\}$. Now $|X-Z| = 1$ and $|Y-Z|=|Y-X|-1$, so repeat this process until $|X-Y|=|Y-X| \leq 1$ for each pair of adjacent bags. Finally, if $XY$ is an edge and $|X-Y|=0$, then contract the edge $XY$, and let the bag at the contracted node be $X$. Repeat this process so that if $X$ and $Y$ are a pair of adjacent bags, then $|X-Y|=|Y-X|=1$. All of these operations preserve tree decomposition properties and width. Hence this modified $T$ is our desired normalised tree decomposition.

A *$k$-colouring* of a graph $G$ is a function that assigns one of $k$ colours to each vertex of $G$ such that no pair of adjacent vertices are assigned the same colour. The *chromatic number* $\chi(G)$ is the minimum number $k$ such that $G$ has a $k$-colouring.

A graph $H$ is a *minor* of a graph $G$ if a graph isomorphic to $H$ can be constructed from $G$ by vertex deletion, edge deletion and edge contraction. *Edge contraction* means to take an edge $vw$ and replace $v$ and $w$ with a new vertex $x$ adjacent to all vertices originally adjacent to $v$ or $w$. If $H$ is a minor of $G$, say that $G$ has an $H$-minor.

The *Hadwiger number* ${\textsf{\textup{had}}}(G)$ is the order of the largest complete minor of $G$. The Hadwiger number is most relevant to *Hadwiger’s Conjecture* [@Hadwiger43], often considered one of the most important unsolved conjectures in graph theory, which states that $\chi(G) \leq {\textsf{\textup{had}}}(G)$. Hadwiger’s Conjecture can be seen as an extension of the Four Colour Theorem, since every planar graph has ${\textsf{\textup{had}}}(G) \leq 4$. While the conjecture remains unsolved in general, it has been proved for ${\textsf{\textup{had}}}(G) \leq 5$ [@RST-Comb93].

Given a graph $H$, an *$H$-model* of $G$ is a set of pairwise vertex-disjoint connected subgraphs of $G$, called *branches*, indexed by the vertices of $H$, such that if $vw \in E(H)$, then there exists an edge between the branches indexed by $v$ and $w$. If $G$ has an $H$-model, then repeatedly contract the edges inside each branch and delete extra vertices and edges to obtain a copy of $H$. Thus if $G$ has an $H$-model, then $H$ is a minor of $G$. Similarly, if $H$ is a minor of $G$, “uncontract" each vertex in the minor to obtain an $H$-model of $G$. Models are helpful when dealing with questions relating to minors, as they describe how the $H$-minor “sits” in $G$.

Brambles
========

Two subgraphs $A$ and $B$ of a graph $G$ *touch* if $V(A)\cap V(B)\neq\emptyset$, or some edge of $G$ has one endpoint in $A$ and the other endpoint in $B$. A *bramble* in $G$ is a set of connected subgraphs of $G$ that pairwise touch. A set $S$ of vertices in $G$ is a *hitting set* of a bramble ${\ensuremath{\mathcal{B}}}$ if $S$ intersects every element of ${\ensuremath{\mathcal{B}}}$. The *order* of ${\ensuremath{\mathcal{B}}}$ is the minimum size of a hitting set. The *bramble number* of $G$ is the maximum order of a bramble in $G$. Brambles were first defined by @SeymourThomas-JCTB93, where they were called *screens of thickness $k$*. Seymour and Thomas proved the following result.

\[theorem:twdual\] For any graph $G$, $${\textsf{\textup{tw}}}(G) = {\textsf{\textup{bn}}}(G) - 1.$$

Here, we present a short proof showing one direction of this result. The other (more difficult) direction can be found in [@SeymourThomas-JCTB93]; see @ShortDiestel for a shorter proof. Let $\beta$ be a bramble in $G$ of maximum order, and let $T$ be the underlying tree in a tree decomposition of $G$. For a subgraph $A \in \beta$, let $T_{A}$ be the subgraph of $T$ induced by the nodes of $T$ whose bags contain vertices of $A$. Since $A$ is connected, $T_A$ is also connected. Similarly, if $A,B \in \beta$, then since these subgraphs touch, there is a node of $T$ in both $T_A$ and $T_B$. So the set of subtrees $\{ T_A : A \in \beta \}$ pairwise intersect. By the Helly Property of trees, there is some node $x$ that is in all such $T_A$. The bag indexed by $x$ contains a vertex from each $A \in \beta$, so it is a hitting set of $\beta$. Hence that bag has order at least ${\textsf{\textup{bn}}}(G)$, and so ${\textsf{\textup{tw}}}(G) \geq {\textsf{\textup{bn}}}(G) - 1$.

Note that this means that the bramble number is equal to the size of the largest bag in a minimum width tree decomposition.

Brambles are useful for finding a lower bound on the treewidth of a graph. Consider the following: given a valid tree decomposition $T$ for a graph $G$, then ${\textsf{\textup{tw}}}(G)$ is at most the width of $T$. Brambles provide the equivalent functionality for the lower bound — given a valid bramble of a graph $G$, it follows that the bramble number is at least the order of that bramble, giving us a lower bound on the treewidth. (For examples of this, see @bodlaenderbramble, @lucenabramble and Lemma \[lemma:gridbramble\].)

$k$-Trees and Chordal Graphs
============================

In certain applications, such as graph drawing [@DMW05; @DiGiacomo] or graph colouring [@KP-DM08; @Albertson-EJC04], it often suffices to consider only the edge-maximal graphs of a given family to obtain a result. The language of $k$-trees and chordal graphs provides an elegant description of the edge-maximal graphs with treewidth at most $k$.

A vertex $v$ in a graph $G$ is *$k$-simplicial* if it has degree $k$ and its neighbours induce a clique. A graph $G$ is a *$k$-tree* if either:

-   $G = K_{k+1}$

-   $G$ has a $k$-simplicial vertex $v$ and $G-v$ is also a $k$-tree.

Note that there is some discrepancy over this definition; certain authors use $K_{k}$ in the base case. This means that $K_{k}$ is a $k$-tree, but creates no other changes. $k$-trees have a strong tie to treewidth; see Lemma \[lemma:ktree\].

A graph is *chordal* if it contains no induced cycle of length at least four. That is, every cycle that is not a triangle contains a chord. @gavril74 showed that the chordal graphs are exactly the intersection graphs of subtrees of a tree $T$. So construct a tree decomposition with underlying tree $T$ as follows. Think of each $v \in V(G)$ as a subtree of $T$; place $v$ in the bags indexed by the nodes of that subtree. It can easily be seen that this is a tree decomposition of $G$ in which every bag is a clique (that is, every possible edge exists), since should two vertices share a bag, then their subtrees intersect and the vertices are adjacent. It also follows that the graph arising from a tree decomposition with all possible edges (that is, two vertices are adjacent if and only if they share a bag) is a chordal graph. Chordal graphs are therefore interesting by being the edge-maximal graphs for a fixed tree-width.

\[lemma:ktree\] $$\begin{aligned}
{\textsf{\textup{tw}}}(G) &= \min\{ k: G \text{ is a spanning subgraph of a $k$-tree }\}. \\
 &= \min\{ k: G \text{ is a spanning subgraph of a chordal graph with no $(k+2)$-clique }\}.\end{aligned}$$

For simplicity, let $a(G) = \min\{ k: G$ is a spanning subgraph of a $k$-tree$\}$ and $b(G) = \min\{ k: G$ is a spanning subgraph of a chordal graph with no $(k+2)$-clique$\}$.

First, show $b(G) \leq a(G)$. @FG65 showed that a graph $H$ is chordal if and only if it has a *perfect elimination ordering*; that is, an ordering of the vertex set such that for each $v \in V(H)$, $v$ and all vertices adjacent to $v$ which are after $v$ in the ordering form a clique. If $H$ be an $a(G)$-tree such that $G$ is a spanning subgraph of $H$, then there is a simple perfect elimination ordering for $H$. (Repeatedly delete the $a(G)$-simplicial vertices to obtain $K_{a(G)+1}$, and consider the order of deletion.) So $H$ is chordal. It is clear that each $v$ has only $a(G)$ neighbours after it in this ordering, so $H$ has no $(a(G)+2)$-clique. (For any clique, consider the first vertex of the clique in the ordering, and note at most $a(G)$ other vertices are in the clique.) Thus $b(G) \leq a(G)$.

Second, show $a(G) \leq {\textsf{\textup{tw}}}(G)$. Assume for the sake of a contradiction that $G$ is a vertex-minimal counterexample, and say $G$ has treewidth $k$. It is easy to see $a(G) \leq {\textsf{\textup{tw}}}(G)$ when $G$ is complete, so assume otherwise. Let $T$ be a tree decomposition of $G$ with minimum width. By Lemma \[lemma:normal\], assume $T$ is normalised. Note since $G$ is not complete, $T$ contains more than one bag. Let $G'$ be the graph created by taking $G$ and adding all edges $vw$, where $v$ and $w$ share some bag of $T$. So $G$ is a spanning subgraph of $G'$ and $T$ is a tree decomposition of $G'$ as well as $G$. By the normalisation, there is a vertex $v \in V(G')$ such that $v$ appears in a leaf bag $B$ of $T$ and nowhere else. Hence $v$ has exactly $k$ neighbours in $G'$, which form a clique as they are all in $B$. Since it is smaller than the minimal counterexample, $a(G'-v) \leq {\textsf{\textup{tw}}}(G'-v) \leq k$. Since $G'-v$ contains a $(k+1)$-clique (consider a bag of $T$ other than $B$), it follows $a(G'-v) \geq k$. Thus $a(G'-v)=k$, and $G'-v$ is a spanning subtree of a $k$-tree $H$. As $v$ is $k$-simplicial in $G'$, it follows $G'$ (and thus $G$) is a spanning subgraph of a $k$-tree, which contradicts our assumption. Finally, show ${\textsf{\textup{tw}}}(G) \leq b(G)$. $G$ is a spanning subgraph of a $H$, chordal graph with no $(b(G)+2)$-clique. There is a tree decomposition of $H$ where every bag is a clique; this means it has width at most $b(G)$. This tree decomposition is also a tree decomposition for $G$, so ${\textsf{\textup{tw}}}(G) \leq b(G)$.

Hence, it follows that $b(G) \leq a(G) \leq {\textsf{\textup{tw}}}(G) \leq b(G)$, which is sufficient to prove our desired result.

Separators {#section:separators}
==========

For a graph $G$, a set $S \subseteq V(G)$, and some $c \in [\frac{1}{2},1)$, a $(k,S,c)$-*separator* is a set $X \subseteq V(G)$ with $|X| \leq k$, such that no component of $G-X$ contains more than $c|S-X|$ vertices of $S$. Note that a $(k,S,c)$-separator is also a $(k,S,c')$-separator for all $c' \geq c$. Define the *separation number* ${\textsf{\textup{sep}}}_c(G)$ to be the minimum integer $k$ such that there is a $(k,S,c)$-separator for all $S \subseteq V(G)$. We also consider the following variant: a $(k,S,c)^*$-*separator* is a set $X \subseteq V(G)$ with $|X| \leq k$ such that no component of $G-X$ contains more than $c|S|$ vertices of $S-X$. Define ${\textsf{\textup{sep}}}_c^*(G)$ analogously to ${\textsf{\textup{sep}}}_c(G)$, but with respect to these variant separators. It follows from the definition that ${\textsf{\textup{sep}}}_c^*(G) \leq {\textsf{\textup{sep}}}_c(G)$.

Separators can be seen as a generalisation of the ideas presented in the famous planar separator theorem [@LT79], which essentially states that a planar graph $G$ with $n$ vertices has a $(O(\sqrt{n}),V(G),\frac{2}{3})^*$-separator. Unfortunately, the precise definition of a separator and the separation number is inconsistent across the literature. The above definition is an attempt to unify all existing definitions. @RS-GraphMinorsII-JAlg86 gave the first lower bound on ${\textsf{\textup{tw}}}(G)$ in terms of separators, though they do not use the term, nor do they give an explicit definition of separation number. This definition is equivalent to our standard definition but with $c$ fixed at $\frac{1}{2}$. @GM-JCTB, give the above variant definition, with $c$ fixed at $\frac{1}{2}$, and instead call it a *balanced separator*. @Reed97 defines separators using our standard definition, with $c=\frac{2}{3}$. @Bodlaender-TCS98 defines type-1 and type-2 separators, which have variable proportion (i.e. allow for different values of $c$), but are not defined on sets other than $V(G)$. Sometimes [@Fox11; @GM-JCTB; @Bodlaender-TCS98] instead of considering components in $G-X$, separators are defined as partitioning the vertex set of $G-X$ into exactly two parts $A$ and $B$, such that no edge has an endpoint in both parts and $|A \cap S|,|B \cap S| \leq c|S|$. (In fact, @Bodlaender-TCS98 uses both this definition and the standard “components of $G-X$" definition as the difference between type-1 and type-2 separators.) As long as $c \geq \frac{2}{3}$, this is equivalent to considering the components, since Lemma \[lemma:comptrick\] and Corollary \[corollary:comptrick\] allow partitioning of the components into parts $A$ and $B$. However, for lower values of $c$ this no longer holds, for example, if $c=\frac{1}{2}$, it is possible that each component contains exactly $\frac{1}{3}$ of the vertices of $S$, so there is no acceptable partition into $A$ and $B$. As a result, $c=\frac{2}{3}$ and $c=\frac{1}{2}$ are the most “natural" choices for $c$.

Fortunately, ${\textsf{\textup{sep}}}_c(G),{\textsf{\textup{sep}}}_c^*(G),{\textsf{\textup{sep}}}_{c'}(G)$ and ${\textsf{\textup{sep}}}_{c'}^*(G)$ are all tied for all $c,c' \in [\frac{1}{2},1)$. [^4]

@RS-GraphMinorsII-JAlg86 proved that $${\textsf{\textup{sep}}}_{\frac{1}{2}}(G)\leq {\textsf{\textup{tw}}}(G)+1\enspace.$$ (Of course, they did not use our notation.) @RS-GraphMinorsII-JAlg86 [@RS-GraphMinorsXIII-JCTB95] also proved that $${\textsf{\textup{tw}}}(G)+1\leq 4\,{\textsf{\textup{sep}}}_{\frac{2}{3}}(G) - 2\enspace.$$ (@Reed97 [@Reedktreefinder] gives a more accessible proof of this upper bound.) We now provide a series of lemmas to prove a slightly stronger result, that replaces the multiplicative constant “4" by “3".

First, we prove a useful lemma for dealing with components of a graph.

\[lemma:comptrick\] For every graph $G$ and for all sets $X, S \subseteq V(G)$ such that no component of $G-X$ contains more than half of the vertices of $S-X$, it is possible to partition the components of $G-X$ into at most three parts such that no part contains more than half the vertices of $S-X$.

If $G-X$ has at most three components, the claim follows immediately. Hence assume $G-X$ has at least four components. Initially, let each part simply contain a single component. Merge parts as long as the merge does not cause the new part to contain more than half the vertices of $S-X$. Now if two parts contain more than $\frac{1}{4}$ of the vertices of $S-X$ each, then all other parts (of which there must be at least two) contain, in total, less than $\frac{1}{2}$ of the vertices of $S-X$. Then merge all other parts together, leaving the partition with exactly three parts. Alternatively only one part (at most) contains more than $\frac{1}{4}$ of the vertices of $S-X$. So at least three parts contain at most $\frac{1}{4}$ of the vertices of $S-X$, and so merge two of them. This lowers the number of parts in the partition. As long as there are four or more parts, one of these operations can be performed, so repeat until at most three parts remain.

\[corollary:comptrick\] For every graph $G$ and for all sets $X, S \subseteq V(G)$ such that no component of $G-X$ contains more than two-thirds of the vertices of $S-X$, it is possible to partition the components of $G-X$ into at most two parts such that no part contains more than two-thirds the vertices of $S-X$.

This corollary follows by a very similar argument to Lemma \[lemma:comptrick\].

The following argument is similar to that provided in [@RS-GraphMinorsII-JAlg86].

\[lemma:sepleqtw\] For any graph $G$ and for all $c \in [\frac{1}{2},1)$, $${\textsf{\textup{sep}}}_c(G) \leq {\textsf{\textup{tw}}}(G)+1.$$

Fix $S \subseteq V(G)$ and let $k := {\textsf{\textup{tw}}}(G)+1$. It is sufficient to construct a $(k,S,\frac{1}{2})$-separator for $G$. $G$ has a normalised tree decomposition $T$ with maximum bag size $k$, by Lemma \[lemma:normal\]. Consider a pair of adjacent bags $X,Y$. Let $T_X$ and $T_Y$ be the subtrees of $T-XY$ containing bags $X$ and $Y$ respectively. Let $U_X \subseteq V(G)$ be the set of vertices only appearing in bags of $T_X$, and $U_Y$ the set of vertices only appearing in bags of $T_Y$. Then $U_X, X \cap Y, U_Y$ is a partition of $V(G)$ such that no edge has an endpoint in $U_X$ and $U_Y$. Each component of $G-(X \cap Y)$ is contained entirely within $U_X$ or $U_Y$. Say $Q \subseteq V(G)$ is *large* if $|Q \cap S| > \frac{1}{2}|S-(X \cap Y)|$.

If neither $U_X$ or $U_Y$ is large, then no component of $G-(X \cap Y)$ is large. Hence $X \cap Y$ is a $(|X \cap Y|, S,\frac{1}{2})$-separator. Since $|X \cap Y| \leq |Y| \leq k$, this is sufficient.

Alternatively, for all edges $XY \in E(T)$, exactly one of $U_X$ and $U_Y$ is large. (If both sets are large, then $|S-(X \cap Y)| = |U_X \cap S| + |U_Y \cap S| > |S-(X \cap Y)|$, which is a contradiction.) Orient the edge $XY \in E(T)$ towards $X$ if $U_X$ is large, or towards $Y$ if $U_Y$ is large.

Now there must be a bag $B$ with outdegree 0. If $B$ is a $(|B|, S,\frac{1}{2})$-separator, then as $|B|=k$, the result is achieved. Otherwise, exactly one component $C$ of $G-B$ is large. The vertices of $C$ only appear in the bags of a single subtree of $T-B$. Label that subtree as $T'$, and let $A$ denote the bag of $T'$ adjacent to $B$. Recall there is a partition $V(G)$ into $U_A, A \cap B, U_B$ where $|U_B \cap S| > \frac{1}{2}|S-(A \cap B)|$, since the edge $AB$ is oriented towards $B$. Hence $|U_A \cap S| < \frac{1}{2}|S-(A \cap B)|$. Also note the vertices of $G-B$ that only appear in the bags of $T'$ are exactly the vertices of $U_A$. Hence $C \subseteq U_A$, and $|U_A \cap S| > \frac{1}{2}|S-B|$.

So $\frac{1}{2}|S-B| < |U_A \cap S| < \frac{1}{2}|S-(A \cap B)|$. By our normalisation, $|A \cap B| = |B|-1$. So $|S-B| \geq |S-(A \cap B)|-1$. Thus $|S-(A \cap B)|-1 < 2|U_A \cap S| < |S-(A \cap B)|$, which is a contradiction as $|S-(A \cap B)|-1$, $2|U_A \cap S|$ and $|S-(A \cap B)|$ are all integers.

Now we provide a proof of the upper bound.

For any graph $G$, for all $c \in [\frac{1}{2},1)$, $${\textsf{\textup{bn}}}(G) \leq \frac{1}{1-c}{\textsf{\textup{sep}}}_c^*(G).$$

Say $\beta$ is an optimal bramble of $G$ with a minimum hitting set $H$. That is, $|H|={\textsf{\textup{bn}}}(G)$. For the sake of a contradiction, assume that $(1-c){\textsf{\textup{bn}}}(G) > {\textsf{\textup{sep}}}_c^*(G)$. So there is a $({\textsf{\textup{sep}}}_c^*(G),H,c)^*$-separator $X$. If $X$ is a hitting set for $\beta$ then ${\textsf{\textup{bn}}}(G) \leq |X| \leq sep_c^*(G) < (1-c){\textsf{\textup{bn}}}(G)$, which is a contradiction. So $X$ is not a hitting set for $\beta$. Thus some bramble element of $\beta$ is entirely within a component of $G-X$. Only one such component can contain bramble elements. Call this component $C$. Then we can hit every bramble element of $\beta$ with the vertices of $X$ or the vertices of $H$ inside $C$, that is, $X \cup (H \cap V(C))$ is a hitting set. Since $X$ is a $({\textsf{\textup{sep}}}_c^*(G),H,c)^*$-separator, $|H \cap V(C)| \leq c|H|$. Thus $|X \cup (H \cap V(C))| = |X| + |H \cap V(C)| \leq |X| + c|H| \leq {\textsf{\textup{sep}}}_c^*(G) + c|H| < (1-c)|H| + c|H| = |H|$. Thus $X \cup (H \cap V(C))$ is a hitting set smaller than the minimum hitting set, a contradiction.

Hence, from the above it follows that for $c \in [\frac{1}{2},1)$, $${\textsf{\textup{sep}}}_c^*(G) \leq {\textsf{\textup{sep}}}_c(G) \leq {\textsf{\textup{tw}}}(G) + 1 = {\textsf{\textup{bn}}}(G) \leq \frac{1}{1-c}{\textsf{\textup{sep}}}_c^*(G) \leq \frac{1}{1-c}{\textsf{\textup{sep}}}_c(G).$$

Each of the above inequalities is tight. For a fixed $c \in [\frac{1}{2},1)$, let $k,n$ be integers such that $k > \frac{c}{1-c}+1$ and $n \geq \frac{k-1}{1-c}$. Then ${\textsf{\textup{sep}}}_c^*(\psi_{n,k}) = {\textsf{\textup{sep}}}_c(\psi_{n,k}) = n$, which proves that the first and last inequalities are tight. (See @thesis for a proof of this result.) The remaining two inequalities are tight due to the complete graph $K_n$.

Branchwidth and Tangles
=======================

A *branch decomposition* of a graph $G$ is a pair $(T, \theta)$ where $T$ is a tree with each node having degree 3 or 1, and $\theta$ is a bijective mapping from the edges of $G$ to the leaves of $T$. A vertex $x$ of $G$ is *across* an edge $e$ of $T$ if there are edges $xy$ and $xz$ of $G$ mapped to leaves in different subtrees of $T-e$. The *order* of an edge $e$ of $T$ is the number of edges of $G$ across $e$. The *width* of a branch decomposition is the maximum order of an edge. Finally, the *branchwidth* ${\textsf{\textup{bw}}}(G)$ of a graph $G$ is the minimum width over all branch decompositions of $G$. Note that if $|E(G)| \leq 1$, there are no branch decompositions of $G$, in which case we define ${\textsf{\textup{bw}}}(G)=0$. @RS-GraphMinorsX-JCTB91 first defined branchwidth, where it was defined more generally for hypergraphs; here we just consider the case of simple graphs. Tangles were first defined by @RS-GraphMinorsX-JCTB91. Their definition is in terms of sets of separations of graphs. (Note, importantly, that a *separation* is not the same as a *separator* as defined in Section \[section:separators\].) We omit their definition and instead present the following, initially given by @Reed97.

A set $\tau$ of connected subgraphs of a graph $G$ is a *tangle* if for all sets of three subgraphs $A,B,C \in \tau$, there exists either a vertex $v$ of $G$ in $V(A \cap B \cap C)$, or an edge $e$ of $G$ such that each of $A,B$ and $C$ contain at least one endpoint of $e$. Clearly a tangle is also a bramble—this is the main advantage of this definition. The *order* of a tangle is equal to its order when viewed as a bramble. The *tangle number* ${\textsf{\textup{tn}}}(G)$ is the maximum order of a tangle in $G$.

When defined with respect to hypergraphs, treewidth and tangle number are tied to the maximum of branchwidth and the size of the largest edge. So for simple graphs, there are a few exceptional cases when ${\textsf{\textup{bw}}}(G) < 2$, which we shall deal with briefly. If $G$ is connected and ${\textsf{\textup{bw}}}(G) \leq 1$, then $G$ has at most one vertex with degree greater than 1 (that is, $G$ is a star), and ${\textsf{\textup{bn}}}(G)={\textsf{\textup{tn}}}(G) \leq 2$. Henceforth, assume ${\textsf{\textup{bw}}}(G) \geq 2$.

@RS-GraphMinorsX-JCTB91 prove the following relation between tangle number and branchwidth; we omit the proof. Instead we show that ${\textsf{\textup{tn}}}(G),{\textsf{\textup{bw}}}(G),{\textsf{\textup{bn}}}(G)$ and ${\textsf{\textup{tw}}}(G)$ are all tied by small constant factors.

\[theorem:tangbw\] For a graph $G$, if ${\textsf{\textup{bw}}}(G) \geq 2$, then $${\textsf{\textup{bw}}}(G) = {\textsf{\textup{tn}}}(G).$$

@RS-GraphMinorsX-JCTB91 proved that ${\textsf{\textup{bn}}}(G) \leq \frac{3}{2}{\textsf{\textup{tn}}}(G)$. @Reed97 provided a short proof that ${\textsf{\textup{bn}}}(G) \leq 3\,{\textsf{\textup{tn}}}(G)$. Here, we modify Reed’s proof to show that ${\textsf{\textup{bn}}}(G) \leq 2\,{\textsf{\textup{tn}}}(G)$.

For every graph $G$, $${\textsf{\textup{tn}}}(G)\leq {\textsf{\textup{bn}}}(G)\leq 2\,{\textsf{\textup{tn}}}(G).$$

Since every tangle is also a bramble, ${\textsf{\textup{tn}}}(G) \leq {\textsf{\textup{bn}}}(G)$.

To prove that ${\textsf{\textup{bn}}}(G) \leq 2\,{\textsf{\textup{tn}}}(G)$, let $k:={\textsf{\textup{bn}}}(G)$, and say $\beta$ is a bramble of $G$ of order $k$. Consider a set $S \subseteq V(G)$ with $|S| < k$. If two components of $G-S$ entirely contain a bramble element of $\beta$, then those two bramble elements do not touch. Alternatively, if no component of $G-S$ entirely contains a bramble element, then all bramble elements use a vertex in $S$, and $S$ is a hitting set of smaller order than the minimum hitting set. Thus exactly one component $S'$ of $G-S$ entirely contains a bramble element of $\beta$. Clearly, $V(S') \cap S = \emptyset$.

Define $\tau := \{ S' : S \subseteq V(G), |S| < \frac{k}{2} \}$. To prove that $\tau$ is a tangle, let $T_1, T_2, T_3$ be three elements of $\tau$. Say $T_i = S'_i$ for each $i$. Since $|S_1 \cup S_2| < k$, some bramble element $B_1$ of $\beta$ does not intersect $S_1 \cup S_2$. Similarly, some bramble element $B_2$ does not intersect $S_2 \cup S_3$. Since $B_1$ does not intersect $S_1$, it is entirely within one component of $G-S_1$, that is, $B_1 \subseteq T_1$. Similarly, $B_1 \subseteq T_2$ and $B_2 \subseteq T_2 \cap T_3$. Since $B_1,B_2 \in \beta$, they either share a vertex $v$, or there is an edge $e$ with one endpoint in $B_1$ and the other in $B_2$. In the first case, $v \in V(T_1 \cap T_2 \cap T_3)$. In the second case, one endpoint of $e$ is in $T_1 \cap T_2$, the other in $T_2 \cap T_3$. It follows that $\tau$ is a tangle. The order of $\tau$ is at least $\frac{k}{2}$, since a set $X$ of size less than $\frac{k}{2}$ has a defined $X' \in \tau$, and so $X$ does not intersect all subgraphs of $\tau$. Then ${\textsf{\textup{tn}}}(G) \geq \frac{k}{2}$.

We now provide a proof for a direct relationship between branchwidth and treewidth. Note again these proofs are modified versions of those in [@RS-GraphMinorsX-JCTB91].

\[lemma:twbranch\] For a graph $G$, if ${\textsf{\textup{bw}}}(G) \geq 2$ then $${\textsf{\textup{bw}}}(G) \leq {\textsf{\textup{tw}}}(G)+1 \leq \frac{3}{2}\,{\textsf{\textup{bw}}}(G).$$

We prove the second inequality first. Assume no vertex is isolated. Let $k:= {\textsf{\textup{bw}}}(G)$, and let $(T,\theta)$ be a branch decomposition of order $k$. We construct a tree decomposition with $T$ as the underlying tree, and where $B_x$ will denote the bag indexed by each node $x$ of $T$. A node $x$ in $T$ has degree 3 or 1. If $x$ has degree 1, then let $B_{x}$ contain the two endpoints of $e = \theta^{-1}(x)$. If $x$ has degree 3, then let $B_{x}$ be the set of vertices that are across at least one edge incident to $x$. We now show that this is a tree decomposition. Every vertex appears at least once in the tree decomposition. Also, for every edge $vw \in E(G)$, the bag of the leaf node $\theta(vw)$ contains both $v$ and $w$. If we consider vertex $v \in V(G)$ incident with $vw$ and $vu$, then $v$ is across every edge in $T$ on the path from $\theta(vw)$ to $\theta(vu)$. Thus, $v$ is in every bag indexed by a node on that path. Such a path exists for all neighbours $w,u$ of $v$. It follows that the subtree of nodes indexing bags containing $v$ form a subtree of $T$. Thus $(T, (B_x)_{x \in V(T)})$ is a tree decomposition of $G$. A bag indexed by a leaf node has size 2. If $x$ is not a leaf, then $B_x$ contains the vertices that are across at least one edge incident to $x$. Suppose $v$ is across exactly one such edge $e$. Then there exists $\theta(vw)$ and $\theta(vu)$ in different subtrees of $T-e$. Without loss of generality, $\theta(vw)$ is in the subtree containing $x$. But then the path from $x$ to $\theta(vw)$ uses one of the other two edges incident to $x$. Hence if $v$ is in $B_{x}$ then $v$ is across at least two edges incident to $x$. If the sets of vertices across the three edges incident to $x$ are $A,B$ and $C$ respectively, then $|A| + |B| + |C| \geq 2|B_{x}|$. But $|A|+|B|+|C| \leq 3k$. Therefore, regardless of whether $x$ is a leaf, $|B_{x}| \leq \max\{2,\frac{3}{2}k\} =\frac{3}{2}k$ (since $k \geq 2$). Therefore ${\textsf{\textup{tw}}}(G)+1 \leq \frac{3}{2}k$.

Now we prove the first inequality. Let $k:={\textsf{\textup{tw}}}(G)+1$. Hence there exists a tree decomposition $(T, (B_x)_{x \in V(T)})$ with maximum bag size $k$; choose this tree decomposition such that $T$ is node-minimal, and such that the subtree induced by $\{ x \in V(T) : v \in B_x\}$ is also node-minimal for each $v \in V(G)$. If $k < 2$, then $G$ contains no edge, and ${\textsf{\textup{bw}}}(G) = 0$. Now assume $k \geq 2$ and $E(G) \neq \emptyset$. As this result is trivial when $G$ is complete, we assume otherwise, and thus $T$ is not a single node.

Note the following facts: if $x$ is a node of $T$ with degree 2, then there exists some pair of adjacent vertices $v,w$ such that $B_x$ is the only bag containing $v$ and $w$. (Otherwise, $T$ would violate the minimality properties.) Similarly, if $x$ is a leaf node, then there exists some $v \in V(G)$ such that $B_x$ is the only bag containing $v$. $B_x$ also contains the neighbours of $v$, but nothing else.

Now, for every edge $vw \in E(G)$, choose some bag $B_x$ containing $v$ and $w$. Unless $x$ is a leaf with $B_x = \{v,w\}$, add to $T$ a new node $y$ adjacent to $x$, such that $B_y = \{v,w\}$. Clearly $(T, (B_x)_{x \in V(T)})$ is still a tree decomposition of the same width. From our above facts, every leaf node is either newly constructed or was already of the form $B_x = \{v,w\}$. Also, every node that previously had degree 2 now has higher degree. A node that was previously a leaf either remains a leaf, or now has degree at least 3. So no node of the new $T$ has degree 2.

If a node $x$ has degree greater than 3, then delete the edges from $x$ to two of its neighbours (denoted $y,z$), and add to $T$ a new node $s$ adjacent to $x,y$ and $z$. Let $B_s := B_x \cap (B_y \cup B_z)$. Clearly this is still a tree decomposition of the same width. Now the degree of $x$ has been reduced by 1, and the new node has degree 3. Repeat this process until all nodes have either degree 3 or 1.

Since each leaf bag contains exactly the endpoints of an edge (and no edge has both endpoints in more than one leaf), there is a bijective mapping $\theta$ that takes $vw \in E(G)$ to the leaf node containing $v$ and $w$. Together with $T$, this gives a branch decomposition of $G$. If $xy \in E(T)$, then all edges of $G$ across $xy$ are in $B_x \cap B_y$. So the order of this branch decomposition is at most $k$. Thus ${\textsf{\textup{bw}}}(G) \leq {\textsf{\textup{tw}}}(G)+1$.

(Note that our minimality properties would imply that $|B_x \cap B_y| < k$, however converting the tree to ensure that all nodes have degree 3 or 1 does not necessarily maintain this.)

@RS-GraphMinorsX-JCTB91 showed the bounds in Lemma \[lemma:twbranch\] are tight. To show this, we shall use Theorem \[theorem:tangbw\] and consider the bounds in terms of ${\textsf{\textup{tn}}}(G)$. $K_n$ exhibits the upper bound on ${\textsf{\textup{tw}}}(G)$ when $n$ is divisible by 3; let the tangle contain all subgraphs with more than $\frac{2}{3}n$ vertices. The graph $K_{n,n}$ minus a perfect matching exhibits the lower bound on ${\textsf{\textup{tw}}}(G)$ when $n \geq 4$; let the tangle contain all connected subgraphs with at least $n$ vertices.

Tree Products
=============

Let the *lexicographic tree product number* of $G$, denoted by ${\textsf{\textup{ltp}}}(G)$, be the minimum integer $k$ such that $G$ is a minor of $T[K_k]$ for some tree $T$. Here $T[K_k]$ is the lexicographic product, which is the graph obtained from $T$ by replacing each vertex by a copy of $K_k$ and each edge by a copy of $K_{k,k}$. We now show that ${\textsf{\textup{tw}}}$ and ${\textsf{\textup{ltp}}}$ are within constant factors of each other.

\[lemma:ltp\] For every graph $G$, $${\textsf{\textup{ltp}}}(G)-1\leq {\textsf{\textup{tw}}}(G)\leq2{\textsf{\textup{ltp}}}(G)-1\enspace.$$

First we prove that ${\textsf{\textup{ltp}}}(G)\leq{\textsf{\textup{tw}}}(G)+1$. Consider a tree decomposition of $G$ with width $k:={\textsf{\textup{tw}}}(G)$ whose underlying tree is $T$. Clearly, $G$ is a minor of $T[K_{k+1}]$. Thus ${\textsf{\textup{ltp}}}(G)\leq k+1$.

Now we prove that ${\textsf{\textup{tw}}}(G)\leq2{\textsf{\textup{ltp}}}(G)-1$. Let $T$ be a tree such that $G$ is a minor of $T[K_k]$ where $k:={\textsf{\textup{ltp}}}(G)$. For each vertex $v$ of $T$ let $K_v$ be the copy of $K_k$ that replaces $v$ in the construction of $T[K_k]$. Let $T'$ be the tree obtained from $T$ by subdividing each edge. Now we construct a tree decomposition of $T[K_k]$ whose underlying tree is $T'$. For each vertex $v$ of $T$, let the bag at $v$ consist of $K_v$. For each edge $vw$ of $T$ subdivided by vertex $x$, let the bag at $x$ consist of $K_v\cup K_w$. Thus each edge of $T[K_k]$ is in some bag, and the set of bags that contain each vertex of $T[K_k]$ form a connected subtree of $T'$. Hence we have a tree decomposition of $T'$. Each bag has size at most $2k$. Hence ${\textsf{\textup{tw}}}(T[K_k])\leq 2k-1$. (In fact, ${\textsf{\textup{tw}}}(T[K_k])= 2k-1$ since $T[K_k]$ contains $K_{2k}$.) Thus every minor of $T'$, including $G$, has treewidth at most $2k-1$.

If $T$ is a tree, let $T^{(k)}$ denote the cartesian product of $T$ with $K_k$. That is, the graph with vertex set $\{(x,i): x \in T, i \in \{1, \dots, k\}\}$ and with an edge between $(x,i)$ and $(y,j)$ when $x=y$, or when $xy \in E(T)$ and $i=j$. Then define the *cartesian tree product number* of $G$, ${\textsf{\textup{ctp}}}(G)$, to be the minimum integer $k$ such that $G$ is a minor of $T^{(k)}$. ${\textsf{\textup{ctp}}}(G)$ was first defined by @holst and @yves, however they did not use that name or notation. They also proved the following result. We provide a different proof.

\[lemma:ctp\] For every graph $G$, $${\textsf{\textup{ctp}}}(G)-1 \leq {\textsf{\textup{tw}}}(G) \leq {\textsf{\textup{ctp}}}(G).$$

Let $k:= {\textsf{\textup{tw}}}(G)$. By Lemma \[lemma:ktree\], $G$ is the spanning subgraph of a chordal graph $G'$ that has a $(k+1)$-clique but no $(k+2)$-clique. Let $(T, (B_x \subseteq V(G))_{x \in V(T)})$ be a minimum width tree decomposition of $G'$. This has width $k$ and is also a tree decomposition of $G$. To prove the first inequality, it is sufficient to show that $G$ is a minor of $T^{(k+1)}$. Let $c$ be a $(k+1)$-colouring of $G'$. (It is well-known that chordal graphs are perfect.) For each $v \in V(G)$, define the connected subgraph $R_v$ of $T^{(k+1)}$ such that $R_v := \{(x,c(v)): v \in B_x\}$. If $(x,i) \in V(R_v) \cap V(R_w)$ then both $v$ and $w$ are in $B_x$ and $c(v)=c(w)=i$. But if $v$ and $w$ share a bag then $vw \in E(G')$, which contradicts the vertex colouring $c$. So the subgraphs $R_v$ are pairwise disjoint, for all $v \in V(G)$. If $vw \in E(G)$, then $v$ and $w$ share a bag $B_x$. Hence there is an edge $(x,c(v))(x,c(w))$ between the subgraphs $R_v$ and $R_w$. Hence the $R_v$ subgraphs form a $G$-model of $T^{(k+1)}$.

Now we prove the second inequality. Let $k:= {\textsf{\textup{ctp}}}(G)$, and choose tree $T$ such that $G$ is a minor of $T^{(k)}$. As ${\textsf{\textup{tw}}}(G) \leq {\textsf{\textup{tw}}}(T^{(k)})$, it is sufficient to show that ${\textsf{\textup{tw}}}(T^{(k)}) \leq k$. Let $T'$ be the tree $T$ with each edge subdivided $k$ times. Label the vertices created by subdividing $xy \in E(T)$ as $xy(1), \dots, xy(k)$, such that $xy(1)$ is adjacent to $x$ and $xy(k)$ is adjacent to $y$. Construct $(T', (B_x \subseteq V(G))_{x \in V(T')})$ as follows. For a vertex $x \in T$, let $B_x = \{(x,i) | i \in \{1, \dots, k\}\}$. For a subdivision vertex $xy(j)$, let $B_{xy(j)} = \{(x,i),(y,i') | 1 \leq i' \leq j \leq i \leq k\}$. This is a valid tree decomposition with maximum bag size $k+1$. Hence ${\textsf{\textup{tw}}}(T^{(k)}) \leq k$ as required.

All these bounds are tight. Let $k,n$ be integers such that $n \geq 3$. Then the first inequalities in Lemma \[lemma:ltp\] and Lemma \[lemma:ctp\] are tight for $\psi_{n,k}$ [@thesis]. (Also see @MS for a similar result.) The second inequalities are tight for the complete graph $K_n$ (for Lemma \[lemma:ltp\], ensure that $n$ is even).

Linkedness
==========

@Reed97 introduced the following definition. For a positive integer $k$, a set $S$ of vertices in a graph $G$ is *$k$-linked* if for every set $X$ of fewer than $k$ vertices in $G$ there is a component of $G-X$ that contains more than half of the vertices in $S$. The *linkedness* of $G$, denoted by ${\textsf{\textup{link}}}(G)$, is the maximum integer $k$ for which $G$ contains a $k$-linked set. Linkedness is used by @Reed97 in his proof of the Grid Minor Theorem.

\[lemma:lemmalink\] For every graph $G$, $${\textsf{\textup{link}}}(G)\leq {\textsf{\textup{bn}}}(G)\leq2\,{\textsf{\textup{link}}}(G)\enspace.$$

First we prove that ${\textsf{\textup{link}}}(G)\leq {\textsf{\textup{bn}}}(G)$. Let $k:={\textsf{\textup{link}}}(G)$. Let $S$ be a $k$-linked set of vertices in $G$. Thus, for every set $X$ of fewer than $k$ vertices there is a component of $G-X$ that contains more than half of the vertices in $S$. This component is unique. Call it the *big* component. Let $\beta$ be the set of big components (taken over all such sets $X$). Clearly, any two elements of $\beta$ intersect at a vertex in $S$. Hence $\beta$ is a bramble. Let $H$ be a hitting set for $\beta$. If $|H|<k$ then (by the definition of $k$-linked) there is a component of $G-H$ that contains more than half of the vertices in $S$, implying $H$ does not hit some big component. This contradiction proves that $|H|\geq
k$. Hence $\beta$ is a bramble of order at least $k$. Therefore ${\textsf{\textup{bn}}}(G)\geq k={\textsf{\textup{link}}}(G)$.

Now we prove that ${\textsf{\textup{bn}}}(G)\leq 2\,{\textsf{\textup{link}}}(G)$. Assume for the sake of a contradiction that ${\textsf{\textup{bn}}}(G) > 2\,{\textsf{\textup{link}}}(G)$. Let $k := {\textsf{\textup{link}}}(G)$, so $G$ is not $(k+1)$-linked. Let $H$ be a minimum hitting set for a bramble $\beta$ of $G$ of largest order. Since $H$ is not $(k+1)$-linked, there exists a set $X$ of order at most $k$ such that no component of $G-X$ contains more than half of the vertices in $H$. Note that at most one component of $G-X$ can entirely contain a bramble element of $\beta$ (otherwise two bramble elements do not touch). If no component of $G-X$ entirely contains a bramble element of $\beta$, then $X$ is a hitting set for $\beta$ of order $|X| \leq k < \frac{1}{2}{\textsf{\textup{bn}}}(G)$, which contradicts the order of the minimum hitting set. Finally, if a component of $G-X$ entirely contains some bramble element of $\beta$, then let $H' \subset H$ be the set of vertices of $H$ in that component. Now $H'$ intersects all of the bramble elements contained in the component (since those bramble elements do not intersect any other vertices of $H$), and $X$ intersects all remaining bramble elements, as in the previous case. Thus, $H' \cup X$ is a hitting set for $\beta$. However, $|X| \leq k < \frac{1}{2}{\textsf{\textup{bn}}}(G)$, and by the choice of $X$, $|H'| \leq \frac{1}{2}|H| = \frac{1}{2}{\textsf{\textup{bn}}}(G)$. So $|H' \cup X| = |H'| + |X| < {\textsf{\textup{bn}}}(G)$, again contradicting the order of the minimum hitting set.

When $n$ is even ${\textsf{\textup{link}}}(K_n) = \frac{n}{2}$, so the second inequality is tight. The first inequality is tight since ${\textsf{\textup{link}}}(\psi_{n,k}) = {\textsf{\textup{bn}}}(\psi_{n,k}) = n$ when $k \geq 2$ and $n \geq 3$ [@thesis].

Well-linked and $k$-Connected Sets
==================================

For a graph $G$, a set $S \subseteq V(G)$ is *well-linked* if for every pair $A,B \subseteq S$ such that $|A|=|B|$, there exists a set of $|A|$ vertex-disjoint paths from $A$ to $B$. If we can ensure these vertex-disjoint paths also have no internal vertices in $S$, then $S$ is *externally-well-linked*. The notion of a well-linked set was first defined by @Reed97, while a similar definition was used by @RST-JCTB94. Reed also described externally-well-linked sets in the same paper (but did not define it explicitly) and stated but did not prove that $S$ is well-linked iff $S$ is externally-well-linked. We provide a proof below. Let ${\textsf{\textup{wl}}}(G) := \max\{|S| : S \subseteq V(G), S$ is well-linked$\}$ denote the *well-linked number* of $G$.

\[lemma:extwl\] $S$ is well-linked iff $S$ is externally-well-linked.

It should be clear that if $S$ is externally-well-linked that $S$ is well-linked, so we prove the forward direction. Let $S \subseteq V(G)$ be well-linked. It is sufficient to show that for all $A,B \subseteq S$ with $|A|=|B|$ there are $|A|$ vertex-disjoint paths from $A$ to $B$ that are internally disjoint from $S$. Define $C := S - (A \cup B)$ and $A' := A \cup C$ and $B' := B \cup C$. Now $S = A' \cup B'$. Since $S$ is well-linked and $|A'| = |B'|$, there are $|A'|$ vertex-disjoint paths between $A'$ and $B'$. Each such path uses exactly one vertex from $A'$ and one vertex from $B'$. Thus, if $v \in C \subseteq A \cap B$, then the path containing $v$ must simply be the singleton path $\{v\}$. Thus this path set contains a set of singleton paths for each vertex of $C$ and, more importantly, a set of paths starting in $A'-C = A$ and ending at $B'-C = B$. Since every vertex of $S$ is in either $A'$ or $B'$, and each path starts at a vertex in $A'$ and ends at one in $B'$, no internal vertex of these paths is in $S$. This is the required set of disjoint paths from $A$ to $B$ that are internally disjoint from $S$.

@Reed97 proved that ${\textsf{\textup{bn}}}(G) \leq {\textsf{\textup{wl}}}(G) \leq 4\,{\textsf{\textup{bn}}}(G)$. We provide that proof of the first inequality and modify the proof of the second to give:

\[lemma:welllink\] For every graph $G$, $${\textsf{\textup{bn}}}(G) \leq {\textsf{\textup{wl}}}(G) \leq 3\,{\textsf{\textup{link}}}(G) \leq 3\,{\textsf{\textup{bn}}}(G).$$

We first prove that ${\textsf{\textup{bn}}}(G) \leq {\textsf{\textup{wl}}}(G)$. Assume for the sake of a contradiction that ${\textsf{\textup{wl}}}(G) < {\textsf{\textup{bn}}}(G)$. Let $\beta$ be a bramble of largest order, and $H$ a minimal hitting set of $\beta$. Thus $H$ is not well-linked (since $|H| = {\textsf{\textup{bn}}}(G) > {\textsf{\textup{wl}}}(G)$). Choose $A,B \subseteq H$ such that $|A|=|B|$ but there are not $|A|$ vertex-disjoint paths from $A$ to $B$. By Menger’s Theorem, there exists a set of vertices $C$ with $|C| < |A|$ such that after deleting $C$, there is no $A$-$B$ path in $G$. Now consider a bramble element of $\beta$. If two components of $G-C$ entirely contain bramble elements, then those bramble elements cannot touch. Thus, it follows that at most one component of $G-C$ entirely contains some bramble element. Label this component $C'$; if no such component exists label $C'$ arbitrarily. $C'$ does not contain vertices from both $A$ and $B$, so without loss of generality assume $A \cap C' = \emptyset$. Thus all bramble elements entirely within $C'$ are hit by vertices of $H-A$, and all others are hit by $C$. So $(H-A) \cup C$ is a hitting set for $\beta$, but $|(H-A) \cup C| = |H|-|A|+|C| < |H|$, contradicting the minimality of $H$. Hence ${\textsf{\textup{bn}}}(G) \leq {\textsf{\textup{wl}}}(G)$.

Now we show that ${\textsf{\textup{wl}}}(G) \leq 3\,{\textsf{\textup{link}}}(G)$. For the sake of a contradiction, say $3\,{\textsf{\textup{link}}}(G)< {\textsf{\textup{wl}}}(G)$. Define $k := \frac{1}{3}{\textsf{\textup{wl}}}(G)$. Let $S$ be the largest well-linked set. That is, $|S| = {\textsf{\textup{wl}}}(G)$. By Lemma \[lemma:extwl\] $S$ is externally-well-linked. $S$ is not ${\ensuremath{\protect\lceilk\rceil}}$-linked as ${\textsf{\textup{link}}}(G) < {\ensuremath{\protect\lceilk\rceil}}$. Hence there exists a set $X \subseteq V(G)$ with $|X| < {\ensuremath{\protect\lceilk\rceil}}$ such that $G-X$ has no component containing more than $\frac{1}{2}|S|$ vertices of $S$. Since $|X|$ is an integer, $|X| < k$. Let $a := |X \cap S|$.

Using an argument similar to Lemma \[lemma:comptrick\], the components of $G-X$ can be partitioned into two or three parts, each with at most $\frac{1}{2}|S|$ vertices of $S$. Some part contains at least a third of the vertices of $S-X$. Let $A$ be the set of vertices in $S$ contained in that part, and let $B$ be the set of vertices in $S$ in the other parts of $G-X$. Now $\frac{1}{2}|S| \geq |A| \geq \frac{1}{3}|S-X| = \frac{1}{3}(|S| - a)$, and so $|B| \geq |S| - |S \cap X| - |A| \geq |S| - a - \frac{1}{2}|S|$. Remove vertices arbitrarily from the largest of $A$ and $B$ until these sets have the same order. Hence $|A|=|B|$ and $|A| \geq \min\{\frac{1}{3}(|S| - a), \frac{1}{2}|S| - a\}$. Since $A,B \subseteq S$ and $S$ is externally-well-linked, there are $|A|$ vertex-disjoint paths from $A$ to $B$ with no internal vertices in $S$. Since $A$ and $B$ are in different components of $G-X$, these paths must use vertices of $X$, but more specifically, vertices of $X-S$. Thus there are at most $|X-S|$ such paths. Thus $|A| \leq |X-S| < k-a$.

Either $\frac{1}{3}(|S|-a) \leq |A| < k-a$ or $\frac{1}{2}|S| - a \leq |A| < k-a$, so $|S| < 3k$. However, $|S|={\textsf{\textup{wl}}}(G)=3k$, which is a contradiction.

The final inequality follows from Lemma \[lemma:lemmalink\].

The first inequality in Lemma \[lemma:welllink\] is tight since ${\textsf{\textup{bn}}}(K_n) = {\textsf{\textup{wl}}}(K_n) = n$. We do not know if the second inequality is tight, but ${\textsf{\textup{wl}}}(G) \leq 2\,{\textsf{\textup{bn}}}(G)-2$ would be best possible since ${\textsf{\textup{bn}}}(K_{2n,n}) = n+1$ and ${\textsf{\textup{wl}}}(K_{2n,n}) = 2n$ (the larger part is the largest well-linked set).

@diestelHC defined the following: $S \subseteq V(G)$ is *$k$-connected* in $G$ if $|S| \geq k$ and for all subsets $A,B \subseteq S$ with $|A| = |B| \leq k$, there are $|A|$ vertex-disjoint paths from $A$ to $B$. If we can ensure these vertex-disjoint paths have no internal vertex or edge in $G[S]$, then $S$ is *externally $k$-connected*. This construction was used in [@diestelHC] to prove a short version of the grid minor theorem.

Note the obvious connection to well-linked sets; $X$ is well-linked iff $X$ is $|X|$-connected. Also note that @Diestel00a, in his treatment of the grid minor theorem, provides a slightly different formulation of externally $k$-connected sets, which only requires vertex-disjoint paths between $A$ and $B$ when they are disjoint subsets of $S$. These definitions are equivalent, which can be proven using a similar argument as in Lemma \[lemma:extwl\]. @Diestel00a also does not use the concept of $k$-connected sets, just externally $k$-connected.

@diestelHC prove the following, but due to its similarity between $k$-connected sets and well-linked sets, we omit the proof.

If $G$ has ${\textsf{\textup{tw}}}(G) < k$ then $G$ contains $(k+1)$-connected set of size $\geq 3k$. If $G$ contains no externally $(k+1)$-connected set of size $\geq 3k$, then ${\textsf{\textup{tw}}}(G) < 4k$.

Grid Minors {#section:gridminors}
===========

A key part of the previously mentioned Graph Minor Structure Theorem is as follows: given a fixed planar graph $H$, there exists some integer $r_{H}$ such that every graph with no $H$-minor has treewidth at most $r_{H}$. This cannot be generalised to when $H$ is non-planar, since there exist planar graphs, the grids, with unbounded treewidth. (By virtue of being planar, the grids do not have a non-planar $H$ as a minor.) In fact, since every planar graph is the minor of some grid, it is sufficient to just consider the grids, which leads to the Grid Minor Theorem:

For each integer $k$ there is a minimum integer $f(k)$ such that every graph with treewidth at least $f(k)$ contains the $k \times k$ grid as a minor.

All of our previous sections have provided parameters with linear ties to treewidth. However, the order of the largest grid minor is not linearly tied to treewidth. The initial bound on $f(k)$ by @RS-GraphMinorsV-JCTB86 was an iterated exponential tower. Later, @RST-JCTB94 improved this to $f(k) \leq 20^{2k^5}$. They also note, by use of a probabilistic argument, that $f(k) \geq \Omega(k^2\log k)$. @diestelHC obtained an upper bound of $2^{5k^{5}\log k}$, which is actually slightly worse than the bound provided by Robertson, Seymour and Thomas, but with a more succinct proof. @KenandYusuke proved that $f(k) \leq 2^{O(k^2 \log k)}$, and @SeymourLeaf proved that $f(k) \leq 2^{O(k\log k)}$. Very recently, @CCpoly proved a polynomial bound of $f(k) \leq O(k^{228})$. Together with the following lower bound, this implies that treewidth and the order of the largest grid-minor are polynomially tied.

\[lemma:gridbramble\] If $G$ contains a $k \times k$ grid minor, then ${\textsf{\textup{tw}}}(G) \geq k$.

If $H$ is a minor of $G$ then ${\textsf{\textup{tw}}}(H) \leq {\textsf{\textup{tw}}}(G)$. Thus it suffices to prove that the $k \times k$ grid $H$ has treewidth at least $k$, which is implied if ${\textsf{\textup{bn}}}(H) \geq k+1$. Consider $H$ drawn in the plane. For a subgraph $S$ of $H$, define a *top vertex* of $S$ in the obvious way. (Note it is not necessarily unique.) Similarly define *bottom vertex*, *left vertex* and *right vertex*. Let subgraph $H'$ of $H$ be the top-left $(k-1) \times (k-1)$ grid in $H$. A *cross* is a subgraph containing exactly one row and column from $H'$, and no vertices outside $H'$. Let $X$ denote the bottom row of $H$, and $Y$ the right column without its bottom vertex. Let $\beta:= \{X,Y, \text{ all crosses}\}$. A pair of crosses intersect in two places. There is an edge from a bottom vertex of a cross to $X$ and a right vertex of a cross to $Y$. There is also an edge from the right vertex of $X$ to the bottom vertex of $Y$. Hence $\beta$ is a bramble. If $Z$ is a hitting set for $\beta$, it must contain $k-1$ vertices of $V(H')$, for otherwise a row and column are not hit, and so a cross is not hit. $Z$ must also contain two other vertices to hit $X$ and $Y$. So $|Z| \geq k+1$, as required.

Grid-like Minors
================

A *grid-like-minor of order $t$* of a graph $G$ is a set of paths ${\ensuremath{\mathcal{P}}}$ with a bipartite intersection graph that contains a $K_t$-minor. Note that if the intersection graph of ${\ensuremath{\mathcal{P}}}$ is partitioned $A$ and $B$, then we can think of the set of paths $A$ as being the “rows" of the “grid", and the set $B$ being the “columns". Also note that an actual $k$-by-$k$ grid gives rise to a set ${\ensuremath{\mathcal{P}}}$ with an intersection graph that is complete bipartite and as such contains a complete minor of order $k$+1. Let ${\textsf{\textup{glm}}}(G)$ be the maximum order of a grid-like-minor of $G$. Grid-like-minors were first defined by @ReedWood-EuJC as a weakening of a grid minor; see Section \[section:gridminors\]. As a result of this weakening, it is easier to tie ${\textsf{\textup{glm}}}(G)$ to ${\textsf{\textup{tw}}}(G)$. This notion has also been applied to prove computational intractability results in monadic second order logic; see @MR2904950 [@Ganian14] and @KT10 [@MR2809681].

The *fractional Hadwiger number* ${\textsf{\textup{had}}}_f(G)$ of $G$ is the maximum $h$ for which there is a bramble ${\ensuremath{\mathcal{B}}}$ in $G$, and a weight function $w :{\ensuremath{\mathcal{B}}}\rightarrow\mathbb{R}_{\geq 0}$, such that $h
=\sum_{X\in{\ensuremath{\mathcal{B}}}}w(X)$ and for each vertex $v$, the sum of the weights of the subgraphs in ${\ensuremath{\mathcal{B}}}$ that contain $v$ is at most 1. For example, the branch sets of a $K_{{\textsf{\textup{had}}}(G)}$-minor form a bramble, for which we may weight each vertex by 1. Thus ${\textsf{\textup{had}}}_f(G) \geq {\textsf{\textup{had}}}(G)$. For a positive integer $r$, the *$r$-integral Hadwiger number* ${\textsf{\textup{had}}}_r(G)$ is defined the same as the fractional Hadwiger number, except that all the weights must be multiples of $\frac{1}{r}$.

The graph $G\square K_2$ (that is, the Cartesian product of $G$ with $K_2$) consists of two disjoint copies of $G$ with an edge between corresponding vertices in the two copies.

\[lemma:glmhad\] For every graph $G$ and integer $r\geq2$, $${\textsf{\textup{glm}}}(G) \leq {\textsf{\textup{had}}}(G\square K_2) \leq 3\,{\textsf{\textup{had}}}_r(G) \enspace,$$ and if $r$ is even then $${\textsf{\textup{glm}}}(G) \leq {\textsf{\textup{had}}}(G\square K_2) \leq 2\,{\textsf{\textup{had}}}_r(G) \leq 2\,{\textsf{\textup{had}}}_f(G)\enspace.$$

@ReedWood-EuJC proved that ${\textsf{\textup{glm}}}(G) \leq {\textsf{\textup{had}}}(G\square K_2)$. Here we provide a proof. Let $t:={\textsf{\textup{glm}}}(G)$. It suffices to show there exists a $K_t$-model in $G\square K_2$. Label the vertices of $K_2$ as $1$ and $2$, so a vertex of $G \square K_2$ has the form $(v,i)$ where $v \in V(G)$ and $i \in \{1,2\}$. If $S$ is a subgraph of $G$, define $(S,i)$ to be the subgraph of $G \square K_2$ induced by $\{(v,i) | v \in S\}$. Let $H$ be the intersection graph of a set of paths ${\ensuremath{\mathcal{P}}}$ with bipartition $A,B$, such that $H$ has a $K_t$-minor. For each $P \in {\ensuremath{\mathcal{P}}}$, let $P' := (P,i)$ where $i=1$ if $P \in A$, and $i=2$ if $P \in B$.

If $PQ \in E(H)$, then without loss of generality $P \in A$ and $Q \in B$, and there exists a vertex $v$ such that $v \in V(P) \cap V(Q)$. Then the edge $(v,1)(v,2) \in E(G \square K_2)$ has one endpoint in $P'$ and the other in $Q'$. So $P' \cup Q'$ is connected.

Let $X_1, \dots, X_t$ be the branch sets of a $K_t$-model in $H$. Define $X_i':= \bigcup_{P \in X_i} P'$. Now each $X_i'$ is connected. It is sufficient to show, for $i \neq j$, that $V(X_i' \cap X_j') = \emptyset$ and there exists an edge of $G \square K_2$ with one endpoint in $X_i'$ and the other in $X_j'$. If there exists $v \in V(X_i' \cap X_j')$ then there exists $P'$ such that $v \in P'$ and $P' \in X_i' \cap X_j'$. But then $P \in X_i \cap X_j$, which is a contradiction. So $V(X_i' \cap X_j') = \emptyset$. Also, since $X_1, \dots, X_t$ is a $K_t$-model of $H$, there exists some $PQ \in E(H)$ such that $P \in X_i$ and $Q \in X_j$. From above, there exists an edge between $P'$ and $Q'$ in $G \square K_2$, which is sufficient.

For the other inequalities, let $X_1,\dots,X_t$ be the branch sets of a $K_t$-minor in $G\square
  K_2$, where $t:={\textsf{\textup{had}}}(G\square K_2)$. Let $X'_i$ be the projection of $X_i$ into the first copy of $G$. Thus $X'_i$ is a connected subgraph of $G$. If $X_i$ and $X_j$ are joined by an edge between the two copies of $G$, then $X'_i$ and $X'_j$ intersect. Otherwise, $X_i$ and $X_j$ are joined by an edge within one of the copies $G$, in which case, $X'_i$ and $X'_j$ are joined by an edge in $G$. Thus $X'_1,\dots,X'_t$ is a bramble in $G$. Weight each $X'_i$ by ${\ensuremath{\protect\lfloor\frac{r}{2}\rfloor}}/r$, which is at least $\frac{1}{3}$ and at most $\frac{1}{2}$. Since $X_1,\dots,X_t$ are pairwise disjoint, each vertex of $G$ is in at most two of $X'_1,\dots,X'_t$. Hence the sum of the weights of $X'_i$ that contain a vertex $v$ is at most $1$. Hence ${\textsf{\textup{had}}}_r(G)$ is at least the total weight, which is at least $\frac{t}{3}$. That is, ${\textsf{\textup{had}}}(G\square K_2)\leq 3{\textsf{\textup{had}}}_r(G)$. If $r$ is even then the total weight equals $\frac{t}{2}$ and ${\textsf{\textup{had}}}(G\square K_2)\leq 2\,{\textsf{\textup{had}}}_r(G)$, which is at most $2\,{\textsf{\textup{had}}}_f(G)$ by definition.

\[lemma:hadbn\] For every graph $G$, $${\textsf{\textup{had}}}_f(G) \leq {\textsf{\textup{bn}}}(G)\enspace.$$

Let ${\ensuremath{\mathcal{B}}}$ be a bramble in $G$ and let $w:{\ensuremath{\mathcal{B}}}\rightarrow\mathbb{R}_{\geq 0}$ be a weight function, such that ${\textsf{\textup{had}}}_f(G) =\sum_{X\in{\ensuremath{\mathcal{B}}}}w(X)$ and for each vertex $v$, the sum of the weights of the subgraphs in ${\ensuremath{\mathcal{B}}}$ that contain $v$ is at most 1. Let $S$ be a hitting set for ${\ensuremath{\mathcal{B}}}$. Thus $$|S|=\sum_{v\in S}1
\geq \sum_{v\in S}\sum_{X\in{\ensuremath{\mathcal{B}}}:v\in X}w(X) = \sum_{X\in{\ensuremath{\mathcal{B}}}}|X\cap
S|w(X) \geq \sum_{X\in{\ensuremath{\mathcal{B}}}}w(X) ={\textsf{\textup{had}}}_f(G)\enspace.$$ That is, the order of ${\ensuremath{\mathcal{B}}}$ is at least ${\textsf{\textup{had}}}_f(G)$. Hence ${\textsf{\textup{bn}}}(G) \geq
{\textsf{\textup{had}}}_f(G)$.

Note this lemma is tight; consider $G = K_n$. @Wood-ProductMinor proved that ${\textsf{\textup{had}}}(G\square K_2)\leq 2{\textsf{\textup{tw}}}(G)+2$ and @ReedWood-EuJC proved that ${\textsf{\textup{glm}}}(G) \leq 2{\textsf{\textup{tw}}}(G)+2$. More precisely, Lemma \[lemma:glmhad\] and Lemma \[lemma:hadbn\] imply that $${\textsf{\textup{glm}}}(G) \leq {\textsf{\textup{had}}}(G\square K_2)\leq 2 {\textsf{\textup{had}}}_f(G) \leq 2{\textsf{\textup{bn}}}(G) = 2{\textsf{\textup{tw}}}(G)+2\enspace,$$ and for every integer $r\geq2$, $${\textsf{\textup{glm}}}(G) \leq 3 {\textsf{\textup{had}}}_r(G) \leq 3 {\textsf{\textup{had}}}_f(G) \leq 3{\textsf{\textup{bn}}}(G)
=3{\textsf{\textup{tw}}}(G)+3\enspace.$$ Conversely, @ReedWood-EuJC proved that $${\textsf{\textup{tw}}}(G) \leq c\, {\textsf{\textup{glm}}}(G)^4 \sqrt{ \log {\textsf{\textup{glm}}}(G) }\enspace,$$ for some constant $c$. Thus ${\textsf{\textup{glm}}}$, ${\textsf{\textup{had}}}(G\square K_2)$, ${\textsf{\textup{had}}}_f$, ${\textsf{\textup{had}}}_r$ for each $r\geq2$, and ${\textsf{\textup{tw}}}$ are tied by polynomial functions.

Fractional Open Problems
========================

Given a graph $G$ define a *$b$-fold colouring* for $G$ to be an assignment of $b$ colours to each vertex of $G$ such that if two vertices are adjacent, they have no colours assigned in common. We can consider this a generalisation of standard graph colouring, which is equivalent when $b=1$. A graph $G$ is *$a\!:\!b$-colourable* when there is a $b$-fold colouring of $G$ with $a$ colours in total. Then define the *$b$-fold chromatic number* $\chi_b(G) := \min\{a| G$ is $a\!:\!b$-colourable$\}$. So $\chi_1(G) = \chi(G)$. Then, define the *fractional chromatic number* $\chi_f(G) = \lim_{b \rightarrow \infty} \frac{\chi_b(G)}{b}$. See @SU-FGT97 for an overview of the topic. @ReedSeymour-JCTB98 proved that $\chi_f(G) \leq 2\,{\textsf{\textup{had}}}(G)$. Hence there is a relationship between the fractional chromatic number and Hadwiger’s number. We have $$\chi_f(G)\leq \chi(G)\quad\text{and}\quad{\textsf{\textup{had}}}(G)\leq{\textsf{\textup{had}}}_f(G)\leq{\textsf{\textup{tw}}}(G)+1\enspace.$$

Hadwiger’s Conjecture asserts that $\chi(G)\leq{\textsf{\textup{had}}}(G)$, thus bridging the gap in the above inequalities. Note that $\chi(G)\leq{\textsf{\textup{tw}}}(G)+1$. (Since $G$ has minimum degree at most ${\textsf{\textup{tw}}}(G)$, a minimum-degree-greedy algorithm uses at most ${\textsf{\textup{tw}}}(G)+1$ colours.) Thus the following two questions provide interesting weakenings of Hadwiger’s Conjecture:

$\chi(G)\leq {\textsf{\textup{had}}}_f(G)$.

$\chi_f(G)\leq {\textsf{\textup{had}}}_f(G)$.

Finally, note that the above results prove that ${\textsf{\textup{had}}}_3$ is bounded by a polynomial function of ${\textsf{\textup{had}}}_2$. Is ${\textsf{\textup{had}}}_3(G) \leq c\,{\textsf{\textup{had}}}_2(G)$ for some constant $c$?

Acknowledgements {#acknowledgements .unnumbered}
================

Many thanks to Jacob Fox and Bruce Reed for instructive conversations.

[^1]: Research of D.R.W. is supported by the Australian Research Council.

[^2]: Research of D.J.H. is supported by an Australian Postgraduate Award.

[^3]: Occasionally, other authors use the term *comparable* [@Fox11]

[^4]: @Fox11 defines a separator to be a set $X \subseteq V(G)$ that partitions $V(G)$ into $X \cup A \cup B$ with no $A-B$ edge and $|A|,|B| \leq \frac{2}{3}|V(G)|$. Fox then defines the separation number to be the minimum integer $k$ such that each subgraph of $G$ has a separator of size $k$. However, we will not consider this definition in this paper.
