首页 | 本学科首页   官方微博 | 高级检索  
     


Hadwiger's conjecture for quasi‐line graphs
Authors:Maria Chudnovsky  Alexandra Ovetsky Fradkin
Affiliation: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 vV(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
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号