Conflict-free connection number and size of graphs
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.
- Conflict-free vertex connection number at most 3 and size of graphs
- On conflict-free connection of graphs
- Conflict-free connections of graphs
- Conflict-free connection numbers of line graphs
- Conflict-free (vertex-)connection numbers of graphs with small diameters
- Conflict-free connection number and independence number of a graph
- Conflict-free vertex-connections of graphs
- Conflict-free connection number of random graphs
- The conflict-free vertex-connection number and degree conditions of graphs
- Maximum value of conflict-free vertex-connection number of graphs
- Conflict-free connection numbers of line graphs
- Conflict-free connections of graphs
- Graphs with conflict-free connection number two
- Graphs with rainbow connection number two
- Hardness results for three kinds of colored connections of graphs
- Improved degree conditions for Hamiltonian properties
- Maximal circuits of graphs. I
- On proper-path colorings in graphs
- Proper connection and size of graphs
- Proper connection of graphs
- Rainbow connection in graphs
- Rainbow connection in graphs with minimum degree three
- Rainbow connection in sparse graphs
- Rainbow connection number of dense graphs
- Unique-maximum and conflict-free coloring for hypergraphs and tree graphs
- Conflict-free connections of graphs
- Conflict-free connection numbers of line graphs
- Graphs with conflict-free connection number two
- Conflict-free connection of trees
- Conflict-free vertex connection number at most 3 and size of graphs
- Strong conflict-free connection of graphs
- The conflict-free vertex-connection number and degree conditions of graphs
- Conflict-free connection number of graphs with four bridges
- A survey on conflict-free connection coloring of graphs
- The conflict-free connection number and the minimum degree-sum of graphs
This page was built for publication: Conflict-free connection number and size of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2051890)
