Conflict-free connection number of random graphs

DOI10.1016/J.DAM.2020.01.034MaRDI QIDQ2192106zbMATH OpenOpenAlexFDO

Authors Ran Gu, Xueliang Li

Publication date 29 June 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.03582

zbMATH Keywords

edge-coloringrandom graphsconflict-free connection number

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Abstract: An edge-colored graph $G$ is 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 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. In this paper, we show that almost all graphs have the conflict-free connection number 2. More precisely, let $G(n,p)$ denote the ErdH{o}s-R'{e}nyi random graph model, in which each of the $$ pairs of vertices appears as an edge with probability $p$ independent from other pairs. We prove that for sufficiently large $n$, $cfc(G(n,p))le2$ if $pgefraclogn+alpha(n)n$, where $alpha(n)ightarrowinfty$. This means that as soon as $G(n,p)$ becomes connected with high probability, $cfc(G(n,p))le2$.

Recommendations

• Conflict-free connections of graphs
• Conflict-free colouring of graphs
• Erdős-Gallai-type results for conflict-free connection of graphs.
• Conflict-free vertex connection number at most 3 and size of graphs
• Graphs with conflict-free connection number two

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 17673 (Why is no real title available?)
• (Strong) conflict-free connectivity: algorithm and complexity
• Almost all regular graphs are hamiltonian
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Conflict-free colourings of graphs and hypergraphs
• Conflict-free connection numbers of line graphs
• Conflict-free connections of graphs
• Conflict-free vertex-connections of graphs
• Graph theory
• Graph unique-maximum and conflict-free colorings
• Graphs with conflict-free connection number two
• Hamiltonian circuits in random graphs
• On conflict-free connection of graphs
• On proper-path colorings in graphs
• On rainbow connection
• On rainbow-k-connectivity of random graphs
• On two Hamilton cycle problems in random graphs
• Paths in graphs
• Proper connection number of random graphs
• Proper connection of graphs
• Properly colored connectivity of graphs
• Properties of almost all graphs and complexes
• Rainbow connection in graphs
• Rainbow connection of sparse random graphs
• Unique-maximum and conflict-free coloring for hypergraphs and tree graphs

Cited in

(3)

• Conflict-free colouring of graphs
• Conflict-free connection number and size of graphs
• A survey on conflict-free connection coloring of graphs

This page was built for publication: Conflict-free connection number of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2192106)