Cyclic coloring of plane graphs |
| |
Authors: | Oleg V. Borodin |
| |
Affiliation: | Institute of Mathematics, Novosibirsk, 630090, USSR |
| |
Abstract: | Let G be a plane graph, and let χk(G) be the minimum number of colors to color the vertices of G so that every two of them which lie in the boundary of the same face of the size at most k, receive different colors. In 1966, Ore and Plummer proved that χk(G)2k for any k3. It is also known that χ3(G)4 (Appel and Haken, 1976) and χ4(G)6 (Borodin, 1984). The result in the present paper is: χ5(G)9, χ6(G)11, χ7(G)12, and χk(G)2k − 3 if k8. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|