B‐Coloring of Planar Graphs

ABSTRACT Let denote the minimum number of colors needed to properly color the edges of a graph such that every 4‐cycle is colored with four different colors. Very recently, Gyárfás et al. [3] proved that for a planar graph and for an outerplanar graph except and . They also conjectured that, when is large enough, every planar graph has and every outerplanar graph has . Let be a planar graph. In this paper, we show the following results: (1) ; (2) if ; (3) if ; (4) if is outerplanar and . Results (3) and (4) confirm the conjectures of Gyárfás et al. [3].