The optimal proper connection number of a graph with given independence number

Abstract

An edge-colored connected graph $G$ is properly connected if between every pair of distinct vertices, there exists a path that no two adjacent edges have a same color. Fujita (2019) introduced the optimal proper connection number ${\mathrm{pc}}_{\mathrm{opt}}(G)$ for a monochromatic connected graph $G$, to make a connected graph properly connected efficiently. More precisely, ${\mathrm{pc}}_{\mathrm{opt}}(G)$ is the smallest integer $p+q$ when one converts a given monochromatic graph $G$ into a properly connected graph by recoloring $p$ edges with $q$ colors. In this paper, we show that ${\mathrm{pc}}_{\mathrm{opt}}(G)$ has an upper bound in terms of the independence number $\alpha (G)$. Namely, we prove that for a connected graph $G$, ${\mathrm{pc}}_{\mathrm{opt}}(G)\le \frac{5\alpha (G)-1}{2}$. Moreoevr, for the case $\alpha (G)\le 3$, we improve the upper bound to $4$, which is tight.