$M_2$-EDGE COLORING AND MAXIMUM MATCHING OF GRAPHS
K. Budajov{\'a}, Július Czap · International Journal of Pure and Apllied Mathematics · 2013
An edge coloring ϕ of a graph G is called M 2 -edge coloring if |ϕ(v)| ≤ 2 for every vertex v of G, where ϕ(v) is the set of colors of edges incident with v. Let α(G) denote the size of a maximum matching in G. Every graph G with maximum degree at least 2 has an M 2 -edge coloring with at least α(G) + 1 colors.We prove that this bound is tight even for connected planar graphs.We show that for any n ∈ N and δ ∈ {1, 2, 3, 4, 5} there is a connected planar graph G on at least n vertices with minimum degree δ such that the maximum number of colors used in an M 2 -edge coloring of G is equal to α(G) + 1.