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.
Original language | English (US) |
---|---|
Pages (from-to) | 17-33 |
Number of pages | 17 |
Journal | Journal of Graph Theory |
Volume | 59 |
Issue number | 1 |
DOIs | |
State | Published - Sep 2008 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Geometry and Topology
Keywords
- Claw-free graphs
- Hadwiger's conjecture
- Minors