Projects per year
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 ℓ≥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 3colorable. 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), 873876) for line graphs, and hence 1link graphs. We prove the conjecture for a wide class of ℓlink graphs.
Original language  English 

Pages (fromto)  460476 
Number of pages  17 
Journal  Journal of Graph Theory 
Volume  84 
Issue number  4 
DOIs  
Publication status  Published  2017 
Keywords
 Chromatic number
 Graph minor
 Hadwiger's conjecture
 Path graph
 ℓlink graph
Projects
 3 Finished

Graph colouring via entropy compression
Australian Research Council (ARC)
2/01/14 → 31/12/17
Project: Research

Hadwiger's graph colouring conjecture
Wood, D. & Zhou, S.
Australian Research Council (ARC), University of Melbourne
1/01/12 → 30/04/15
Project: Research

The Structure and Geometry of Graphs
Australian Research Council (ARC)
1/01/08 → 31/12/13
Project: Research