Proper edge colorings of planar graphs with rainbow C4-s

Gyárfás, András and Martin, Ryan Robert and Ruszinkó, Miklós and Sárközy, Gábor (2024) Proper edge colorings of planar graphs with rainbow C4-s. JOURNAL OF GRAPH THEORY, 107 (4). pp. 833-846. ISSN 0364-9024

Preview

Text 2408.09059v2.pdf Download (396kB) | Preview

Abstract

We call a proper edge coloring of a graph G a B-coloring if every 4-cycle of G is colored with four different colors. Let qB(G) denote the smallest number of colors needed for a B-coloring of G. Motivated by earlier papers on B-colorings, here we consider qB(G) for planar and outerplanar graphs in terms of the maximum degree Δ = Δ(G). We prove that qB(G) ≤ 2Δ + 8 for planar graphs, qB(G) ≤ 2Δ for bipartite planar graphs, qB(G) ≤ Δ + 1 for outerplanar graphs with Δ ≥ 4 and conjecture that, for Δ sufficiently large, qB(G) ≤ 2Δ(G) for planar G and qB(G) ≤ Δ(G) for outerplanar G.

Actions (login required)

Edit Item