Premium
Hadwiger's conjecture for quasi‐line graphs
Author(s) -
Chudnovsky Maria,
Fradkin Alexandra Ovetsky
Publication year - 2008
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20321
Subject(s) - combinatorics , mathematics , discrete mathematics , conjecture , line graph , pathwidth , chordal graph , block graph , graph
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 K t + 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, 2008