4 HADWIGER’S CONJECTURE FOR ℓ-LINK GRAPHS
Bin Jia, David, R. Wood · 2016
Abstract 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 in which consecutive edges are different. The ℓ ‐link graph of G is the graph with vertices the ℓ‐links of G , such that two vertices are joined by edges in if they correspond to two subsequences of each of μ ‐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 ℓ, is 3‐colorable. By investigating the shunting of ℓ‐links in G , we show that the Hadwiger number of a nonempty 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.