Conflict-free connection number and size of graphs (Q2051890)

An edge-coloured graph is said to be conflict-free connected if every two distinct vertices are connected by at least one path which contains a colour used on exactly one of its edges. The conflict-free connection number of a graph \(G\), denoted by \(\operatorname{cfc}(G)\), is the smallest number of colours needed in order to make \(G\) conflict-free connected. In this paper the authors solve this problem. For all integers \(n\) and \(k\) with \(1\leq k \leq n-1\), compute and minimise the function \(f_{\mathrm{cfc}}(n,k)\) with the following property: If \(|V(G)| = n\) and \(|E(G)|\geq f_{\mathrm{cfc}}(n,k)\), then \(\operatorname{cfc}(G) \leq k\). For a graph \(G\), let \(C(G)\) be the subgraph of \(G\) induced by its bridges. Then they give the following two main results. \begin{itemize} \item[(1)] Let \(k\geq 2\) and let \(G\) be a connected graph of order \(n\) containing bridges. If \(|E(G)|\geq \binom{n-2k}{2} + 2k + 1\), then \(\operatorname{cfc}(G) \leq k\) or \(\Delta(C(G))\geq k+1\). \item[(2)] Let \(G\) be a connected graph of order \(n\) with \(t\geq 4\) bridges such that \(n\geq t+15\). If \(|E(G)|\geq \binom{n-t-2}{2} + t + 4\), then \(\operatorname{cfc}(G)=2\) or \(G\) belongs to a class of exceptional graphs. \end{itemize} The authors mention that, during the preparation of their paper, a proof of the problem was independently solved in [\textit{M. Ji}, ``Erdős-Gallai type results for conflict-free connection of graphs'', Preprint, \url{arXiv:1812.10701}], to which they refer for a fuller proof of some of their results.