Optimal proper connection of graphs (Q2192984)

An edge-colored graph \(G\) is properly colored if no two adjacent edges share a color in \(G\). An edge-colored connected graph \(G\) is properly connected if between every pair of distinct vertices, there exists a path that is properly colored. In this paper, the author considers the problem to convert a given monochromatic graph into a properly connected graph by recoloring \(p\) edges with \(q\) colors so that \(p + q\) is as small as possible. The author also discusses how this can be done efficiently for some restricted graphs, such as trees, complete bipartite graphs and graphs with independence number 2.