Conflict-free connection number and size of graphs
type: Item
instance of: scholarly article
title: Conflict-free connection number and size of graphs
zbMATH Open document ID: 1482.05101
author: Trung Duy Doan
author: Ingo Schiermeyer
published in: Graphs and Combinatorics
publication date: 2021-11-25T00:00:00Z
review text: 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.
reviewed by: Josef Lauri
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 7433384
zbMATH Keywords: edge-colouring
zbMATH Keywords: conflict-free connection number
zbMATH Keywords: size of graph
MaRDI profile type: Publication
full work available at URL: s00373-021-02331-8
OpenAlex ID: W3165733987
cites work: On proper-path colorings in graphs
cites work: Proper connection of graphs
cites work: Graphs with conflict-free connection number two
cites work: Rainbow connection in graphs
cites work: Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs
cites work: Conflict-free connections of graphs
cites work: Conflict-free connection numbers of line graphs
cites work: Hardness results for three kinds of colored connections of graphs
cites work: Graphs with rainbow connection number two
cites work: Improved degree conditions for Hamiltonian properties
cites work: Rainbow connection in sparse graphs
cites work: Rainbow connections of graphs: a survey
cites work: Rainbow connection number of dense graphs
cites work: Rainbow Connection in Graphs with Minimum Degree Three
cites work: Proper connection and size of graphs
cites work: Maximal circuits of graphs. I
DOI: 10.1007/S00373-021-02331-8
Recommended article: Conflict-free vertex connection number at most 3 and size of graphs
Recommended article: On conflict-free connection of graphs
Recommended article: Conflict-free connections of graphs
Recommended article: Conflict-free connection numbers of line graphs
Recommended article: Conflict-free (vertex)-connection numbers of graphs with small diameters
Recommended article: Conflict-free connection number and independence number of a graph
Recommended article: Conflict-free vertex-connections of graphs
Recommended article: Conflict-free connection number of random graphs
Recommended article: The conflict-free vertex-connection number and degree conditions of graphs
Recommended article: Maximum value of conflict-free vertex-connection number of graphs
description: scientific article; zbMATH DE number 7433384