An edge-colored graph 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 , denoted by , is the smallest number of colors needed in order to make conflict-free connected. For a graph let be the subgraph of induced by its set of cut-edges. In this paper, we first show that, if is a connected non-complete graph of order with being a linear forest and with the minimum degree %, then for $4 \leq n\leq 8 \delta(G)\geq \max{3, \frac{n-4}{5}}cfc(G)=2$. The bound on the minimum degree is best possible. Next, we prove that, if is a connected non-complete graph of order with being a linear forest and with for each pair of two nonadjacent vertices of , then . Both bounds, on the order and the degree sum, are tight. Moreover, we prove several results concerning relations between degree conditions on and the number of cut edges in .

生成讲解博客的中文版本

生成AI智能校验的中文版本