The optimal proper connection number of a graph with given independence number - Fujita, Shinya; Park, Boram (Discrete Optimization, 2021)
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.
Keywords: Connected graph; Connection number; Graph G; Independence number; Recoloring; Upper Bound; Edge-colored graph; Independence number; Optimal proper connection number; Properly connected graph