Graphs with conflict-free connection number two

Abstract

An edge-colored graph $G$ is \emph{conflict-free connected} if any two of its vertices are connected by a path, which contains a color used on exactly one of its edges. The \emph{conflict-free connection number} of a connected graph $G$, denoted by $cfc(G)$, is the smallest number of colors needed in order to make $G$ conflict-free connected. For a graph $G,$ let $C(G)$ be the subgraph of $G$ induced by its set of cut-edges. In this paper, we first show that, if $G$ is a connected non-complete graph $G$ of order $n\ge 9$ with $C(G)$ being a linear forest and with the minimum degree %$\delta (G)\ge 2$, then $cfc(G)=2$ for $4\le n\le 8$; if $\delta (G)\ge \max \{3,\frac{n-4}{5}\}$, then $cfc(G)=2$. The bound on the minimum degree is best possible. Next, we prove that, if $G$ is a connected non-complete graph of order $n\ge 33$ with $C(G)$ being a linear forest and with $d(x)+d(y)\ge \frac{2n-9}{5}$ for each pair of two nonadjacent vertices $x,y$ of $V(G)$, then $cfc(G)=2$. Both bounds, on the order $n$ and the degree sum, are tight. Moreover, we prove several results concerning relations between degree conditions on $G$ and the number of cut edges in $G$.

13 pages