Abstract
We prove that every triangle-free graph whose subgraphs all have average degree less than 12/5 has a circular (5; 2)-coloring. This includes planar and projective-planar graphs with girth at least 12.
Original language | English (US) |
---|---|
Pages (from-to) | 417-426 |
Number of pages | 10 |
Journal | Siberian Electronic Mathematical Reports |
Volume | 5 |
State | Published - 2008 |
Keywords
- triangle-free graph
- projective-planar graph
- circular (k; d)-coloring