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.
All Science Journal Classification (ASJC) codes
- Geometry and Topology
- Claw-free graphs
- Hadwiger's conjecture