Acyclic 4-colorability of planar graphs without cycles of length 4 or 6
2010
Every planar graph is known to be acyclically 5-colorable (O. V. Borodin, 1976), which bound is precise. Some sufficient conditions are also obtained for a planar graph to be acyclically 4-colorable. In particular, the acyclic 4-colorabilitywas proved for the following planar graphs: without 3- and 4-cycles (O. V. Borodin, A. V. Kostochka, and D. R. Woodall, 1999), without 4-, 5-, and 6-cycles (M. Montassier, A. Raspaud, and W. Wang, 2006), and either without 4-, 6-, and 7-cycles or without 4-, 6-, and 8-cycles (M. Chen, A. Raspaud, and W. Wang, 2009). In this paper it is proved that each planar graph with neither 4-cycles nor 6-cycles is acyclically 4-colorable.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
14
References
4
Citations
NaN
KQI