Extremal graphs and classification of planar graphs by MC-numbers

Abstract

An edge-coloring of a connected graph $G$ is called a {\em monochromatic connection coloring} (MC-coloring for short) if any two vertices of $G$ are connected by a monochromatic path in $G$. For a connected graph $G$, the {\em monochromatic connection number} (MC-number for short) of $G$, denoted by $mc(G)$, is the maximum number of colors that ensure $G$ has a monochromatic connection coloring by using this number of colors. This concept was introduced by Caro and Yuster in 2011. They proved that $mc(G)\le m-n+k$ if $G$ is not a $k$-connected graph. In this paper we depict all graphs with $mc(G)=m-n+k+1$ and $mc(G)=m-n+k$ if $G$ is a $k$-connected but not $(k+1)$-connected graph. We also prove that $mc(G)\le m-n+4$ if $G$ is a planar graph, and classify all planar graphs by their monochromatic connectivity numbers.

17 pages