On conflict-free connection of graphs

An edge-colored graph G is conflict-free connected if, between each pair of distinct vertices of G, there exists a path in G containing a color used on exactly one of its edges. The conflict-free connection number of a connected graph G, denoted by cfc(G), is defined as the minimum number of colors that are required in order to make G conflict-free connected. In this paper, we firstly determine all trees T of order n for which cfc(T) = n - t, where t >= 1 and n >= 2t + 2. Secondly, we prove that let G be a graph of order n, then 1 <= cfc(G) <= n - 1, and characterize the graphs G with cfc(G) = 1, n - 4, n - 3, n - 2, n - 1, respectively. Finally, we get the Nordhaus-Gaddum-type result for the conflict-free connection number of graphs, and prove that if G and G are connected graphs of order n (n >= 4), then 4 <= cfc(G) + cfc((G) over bar) <= n and 4 <= cfc(G) . cfc((G) over bar) <= 2(n - 2), moreover, cfc(G) + cfc((G) over bar) = n or cfc(G) . cfc((G) over bar) = 2(n - 2) if and only if one of G and (G) over bar is a tree with maximum degree n - 2 or a path of order 5, and the lower bounds are sharp. (C) 2018 Elsevier B.V. All rights reserved.