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


On circle graphs with girth at least five
Authors:Louis Esperet  Pascal Ochem
Institution:a LaBRI, Université Bordeaux 1, 351 Cours de la Libération, 33405 Talence Cedex, France
b LRI, CNRS, Bât 490 Université Paris-Sud 11, 91405 Orsay Cedex, France
Abstract:Circle graphs with girth at least five are known to be 2-degenerate A.A. Ageev, Every circle graph with girth at least 5 is 3-colourable, Discrete Math. 195 (1999) 229-233]. In this paper, we prove that circle graphs with girth at least g≥5 and minimum degree at least two contain a chain of g−4 vertices of degree two, which implies Ageev’s result in the case g=5. We then use this structural property to give an upper bound on the circular chromatic number of circle graphs with girth at least g≥5 as well as a precise estimate of their maximum average degree.
Keywords:Circle graphs  Maximum average degree  Circular coloring
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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