Acyclic 4-coloring of planar graphs without 4- and 5-cycles |
| |
Authors: | O V Borodin |
| |
Institution: | 1.Sobolev Institute of Mathematics,Novosibirsk,Russia;2.Novosibirsk State University,Novosibirsk,Russia |
| |
Abstract: | Every planar graph is known to be acyclically 5-colorable (O.V.Borodin, 1976). Some sufficient conditions are also obtained
for a planar graph to be acyclically 4- and 3-colorable. In particular, the acyclic 4-colorability was 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,
or without 4-, 5-, and 7-cycles, or without 4-, 5-, and intersecting 3-cycles (M. Montassier, A.Raspaud andW.Wang, 2006),
and without 4-, 5-, and 8-cycles (M. Chen and A.Raspaud, 2009). The purpose of this paper is to prove that each planar graph
without 4- and 5-cycles is acyclically 4-colorable. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|