Every circle graph of girth at least 5 is 3-colourable

✍ Scribed by A.A. Ageev

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 235 KB
• Volume: 195
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(98)00192-7

✦ Synopsis

It is known that every triangle-free (equivalently, of girth at least 4) circle graph is 5-colourable and that there exist examples of these graphs which are not 4-colourable . In this note we show that every circle graph of girth at least 5 is 2-degenerate and, consequently, not only 3-colourable but even 3-choosable.