## 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 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 language | English |
---|---|

Pages (from-to) | 460-476 |

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