Conflict-free connection number of random graphs

DOI10.1016/J.DAM.2020.01.034zbMATH Open1442.05057arXiv1809.03582OpenAlexW3006476046MaRDI QIDQ2192106FDOQ2192106

Authors: Ran Gu, Xueliang Li 

Publication date: 29 June 2020

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

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$.

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

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

zbMATH Keywords

edge-coloringrandom graphsconflict-free connection number

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Title not available (Why is that?)
• On rainbow connection
• Rainbow connections of graphs: a survey
• Rainbow connection in graphs
• Paths in graphs
• On proper-path colorings in graphs
• Hamiltonian circuits in random graphs
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Almost all regular graphs are hamiltonian
• Proper connection of graphs
• On rainbow-\(k\)-connectivity of random graphs
• Conflict-free colourings of graphs and hypergraphs
• On two Hamilton cycle problems in random graphs
• Graph unique-maximum and conflict-free colorings
• Properly Colored Connectivity of Graphs
• Proper connection number of random graphs
• Properties of almost all graphs and complexes
• Rainbow connection of sparse random graphs
• Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs
• Title not available (Why is that?)
• Conflict-free connections of graphs
• Conflict-free connection numbers of line graphs
• On conflict-free connection of graphs
• Graphs with conflict-free connection number two
• Conflict-free vertex-connections of graphs
• (Strong) conflict-free connectivity: algorithm and complexity

Cited In (2)

• 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)