Hadwiger's conjecture for $\ell$-link graphs

Abstract

In this paper we define and study a new family of graphs that generalises the notions of line graphs and path graphs. Let $G$ be a graph with no loops but possibly with parallel edges. An \emph{$\ell$-link} of $G$ is a walk of $G$ of length $\ell ⩾0$ in which consecutive edges are different. We identify an $\ell$-link with its reverse sequence. The \emph{$\ell$-link graph ${\mathbb{L}}_{\ell }(G)$} of $G$ is the graph with vertices the $\ell$-links of $G$, such that two vertices are joined by $\mu ⩾0$ edges in ${\mathbb{L}}_{\ell }(G)$ if they correspond to two subsequences of each of $\mu$ $(\ell +1)$-links of $G$. By revealing a recursive structure, we bound from above the chromatic number of $\ell$-link graphs. As a corollary, for a given graph $G$ and large enough $\ell$, ${\mathbb{L}}_{\ell }(G)$ is $3$-colourable. By investigating the shunting of $\ell$-links in $G$, we show that the Hadwiger number of a nonempty ${\mathbb{L}}_{\ell }(G)$ is greater or equal to that of $G$. Hadwiger's conjecture states that the Hadwiger number of a graph is at least the chromatic number of that graph. The conjecture has been proved by Reed and Seymour (2004) for line graphs, and hence $1$-link graphs. We prove the conjecture for a wide class of $\ell$-link graphs.

18 pages, 2 figures

References in corpus (2)

• Clique Minors in Cartesian Products of Graphs
• A construction of imprimitive symmetric graphs which are not multicovers of their quotients