2019/03/08 by Fujita, Shinya
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1903.03311
An edge-colored graph G is called properly colored if no two adjacent edges share a color in G. An edge-colored connected graph G is called properly connected if between every pair of distinct vertices, there exists a path that is properly colored. In this paper, we discuss how to make a connected graph properly connected efficiently. More precisely, we consider the problem to convert a given monochromatic graph into properly connected by recoloring p edges with q colors so that p+q is as small as possible. We discuss how this can be done efficiently for some restricted graphs, such as trees, complete bipartite graphs and graphs with independence number 2.