| Autor: |
Chudnovsky, Maria, Fradkin, Alexandra Ovetsky |
| Zdroj: |
Journal of Graph Theory; September 2008, Vol. 59 Issue: 1 p17-33, 17p |
| Abstrakt: |
A graph Gis a quasi‐line graph if for every vertex v∈ V(G), the set of neighbors of vin Gcan 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 Gis not t‐colorable then it contains Kt+ 1as 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 |
| Databáze: |
Supplemental Index |
| Externí odkaz: |
|
Plný text