Hadwiger's conjecture for ℓ-Link graphs

In this article, we define and study a new family of graphs that generalizes the notions of line graphs and path graphs. Let G be a graph with no loops but possibly with parallel edges. An ℓ-link of G is a walk of G of length ℓ≥0 in which consecutive edges are different. The ℓ-link graph Lℓ(G) of G is the graph with vertices the ℓ-links of G, such that two vertices are joined by μ≥0 edges in Lℓ(G) if they correspond to two subsequences of each of μ (ℓ+1)-links of G. By revealing a recursive structure, we bound from above the chromatic number of ℓ-link graphs. As a corollary, for a given graph G and large enough ℓ, Lℓ(G) is 3-colorable. By investigating the shunting of ℓ-links in G, we show that the Hadwiger number of a nonempty Lℓ(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 (Eur J Combin 25(6) (2004), 873-876) for line graphs, and hence 1-link graphs. We prove the conjecture for a wide class of ℓ-link graphs.