Planar graph colorings without short monochromatic cycles
Tomáš Kaiser, Riste Škrekovski · Journal of Graph Theory · 2004
Abstract It is well known that every planar graph G is 2‐colorable in such a way that no 3‐cycle of G is monochromatic. In this paper, we prove that G has a 2‐coloring such that no cycle of length 3 or 4 is monochromatic. The complete graph K 5 does not admit such a coloring. On the other hand, we extend the result to K 5 ‐minor‐free graphs. There are planar graphs with the property that each of their 2‐colorings has a monochromatic cycle of length 3, 4, or 5. In this sense, our result is best possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 25–38, 2004