Hadwiger's conjecture for quasi‐line graphs
- 17 June 2008
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 59 (1) , 17-33
Abstract
A graph G is a quasi‐line graph if for every vertex v ∈ V(G), the set of neighbors of v in G can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. Hadwiger's conjecture states that if a graph G is not t‐colorable then it contains Kt + 1 as a minor. This conjecture has been proved for line graphs by Reed and Seymour. We extend their result to all quasi‐line graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 17–33, 2008Keywords
This publication has 9 references indexed in Scilit:
- Claw-free graphs. II. Non-orientable prismatic graphsJournal of Combinatorial Theory, Series B, 2008
- Coloring quasi‐line graphsJournal of Graph Theory, 2006
- Hadwiger’s conjecture for line graphsEuropean Journal of Combinatorics, 2004
- Hadwiger's conjecture forK 6-free graphsCombinatorica, 1993
- Every planar map is four colorable. Part I: DischargingIllinois Journal of Mathematics, 1977
- Every planar map is four colorable. Part II: ReducibilityIllinois Journal of Mathematics, 1977
- Über eine Eigenschaft der ebenen KomplexeMathematische Annalen, 1937
- Zur allgemeinen KurventheorieFundamenta Mathematicae, 1927
- Über Graphen und ihre Anwendung auf Determinantentheorie und MengenlehreMathematische Annalen, 1916