Rainbow matchings in an edge-colored planar bipartite graph

Highlights：

• The anti-Ramsey problem in graphs was introduced by Erdös et al. [3] in 1970s. During the last decades, the anti-Ramsey problem for matchings in several graph classes have been studied extensively. Jendrol’, Schiermeyer and Tu initialized the study of anti-Ramsey problem for matchings in plane triangulations and since then, the anti-Ramsey number of matchings in planar graphs received much attention of researchers.

• In this paper, we consider the existence of rainbow matchings in maximal bipartite planar graphs, that is, the anti-Ramsey number of matchings in maximal bipartite planar graphs. We determine the maximum number of colors appearing in an edge-coloring of maximal bipartite planar graphs with a Hamilton cycle which does not contain any rain bow k-matching. The bounds given are best possible.

摘要

•Given an edge-colored graph G, if any two edges of G receive distinct colors, then we call G a rainbow graph. The anti-Ramsey number AR(G;H) is the maximum integer k in a k-edge-coloring of G that there is no any rainbow H.•The anti-Ramsey problem in graphs was introduced by Erdös et al. [3] in 1970s. During the last decades, the anti-Ramsey problem for matchings in several graph classes have been studied extensively. Jendrol’, Schiermeyer and Tu initialized the study of anti-Ramsey problem for matchings in plane triangulations and since then, the anti-Ramsey number of matchings in planar graphs received much attention of researchers.•In this paper, we consider the existence of rainbow matchings in maximal bipartite planar graphs, that is, the anti-Ramsey number of matchings in maximal bipartite planar graphs. We determine the maximum number of colors appearing in an edge-coloring of maximal bipartite planar graphs with a Hamilton cycle which does not contain any rain bow k-matching. The bounds given are best possible.