Hadwiger's conjecture for ℓ-Link graphs

Bin Jia, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review


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.

Original languageEnglish
Pages (from-to)460-476
Number of pages17
JournalJournal of Graph Theory
Issue number4
Publication statusPublished - 2017


  • Chromatic number
  • Graph minor
  • Hadwiger's conjecture
  • Path graph
  • ℓ-link graph

Cite this