Authors: S. Jendrol', L. Kekeòáková Title: Facial rainbow coloring of plane graphs Source: Discussiones Mathematicae Graph Theory Received 28.03.2017, Revised 19.12.2017, Accepted 19.12.2017, doi: 10.7151/dmgt.2047 | |
Abstract: A vertex coloring of a plane graph G is a facial rainbow coloring if any two vertices of G connected by a facial path have distinct colors. The facial rainbow number of a plane graph G, denoted by rb(G), is the minimum number of colors that are necessary in any facial rainbow coloring of G. Let L(G) denote the order of a longest facial path in G. In the present note we prove that rb(T) ≤ \left⌊ \frac{3}{2}L(T) \right⌋ for any tree T and rb(G) ≤ \left⌈ \frac{5}{3}L(G) \right⌉ for arbitrary simple graph G. The upper bound for trees is tight. For any simple 3-connected plane graph G we have rb(G) ≤ L(G)+5. | |
Keywords: cyclic coloring, rainbow coloring, plane graphs | |
Links: |