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{5alpha(G)-1}{2}$. Moreoevr, for the case $alpha(G)leq 3$, we improve the upper bound to $4$, which is tight.
تحميل البحث