Conflict-Free Connection Numbers of Line Graphs

Abstract

A path in an edge-colored graph is called conflict-free if it contains a color that is used by exactly one of its edges. An edge-colored graph G is conflict-free connected if for any two distinct vertices of G, there is a conflict-free path connecting them. For a connected graph G, the conflict-free connection number of G, denoted by cfc(G), is defined as the minimum number of colors that are required to make G conflict-free connected. In this paper, we investigate the conflict-free connection numbers of connected claw-free graphs, especially line graphs. We use L(G) to denote the line graph of a graph G. In general, the k-iterated line graph of a graph G, denoted by $L^k(G)$, is the line graph of the graph $L^{k-1}(G)$, where $k\ge 2$ is a positive integer. We first show that for an arbitrary connected graph G, there exists a positive integer k such that $cfc(L^k(G))\le 2$. Secondly, we get the exact value of the conflict-free connection number of a connected claw-free graph, especially a connected line graph. Thirdly, we prove that for an arbitrary connected graph G and an arbitrary positive integer k, we always have $cfc(L^{k+1}(G))\le cfc(L^k(G))$, with only the exception that G is isomorphic to a star of order at least 5 and $k=1$. Finally, we obtain the exact values of $cfc(L^k(G))$, and use them as an efficient tool to get the smallest nonnegative integer $k_0$ such that $cfc(L^{k_0}(G))=2$.

Supported by NSFC No. 11371205, 11531011 and 11701311, and NSFQH No. 2017-ZJ-790.