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 等数据库收录! |
|