Hadwiger's conjecture for quasi‐line graphs |
| |
| Authors: | Maria Chudnovsky Alexandra Ovetsky Fradkin |
| |
| Institution: | 1. Columbia University, New York, New York 10027;2. This research was conducted while the author served as a Clay Mathematics Institute Research Fellow. Part of the research was conducted at Princeton University.;3. Princeton University, Princeton, New Jersey 08544 |
| |
| 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, 2008 |
| |
| Keywords: | minors Hadwiger's conjecture claw‐free graphs |
|
|
