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 such that no two adjacent edges have the same color. Fujita (2019) introduced the optimal proper connection number pcopt(G) for a monochromatic connected graph G, to make a connected graph properly connected efficiently. More precisely, pcopt (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 pcopt (G) has an upper bound in terms of the independence number α(G). Namely, we prove that for a connected graph G, pcopt (G) [Formula presented]. Moreover, for the case α(G)≤3, we improve the upper bound to 4, which is tight.