Proper connection number of random graphs

DOI10.1016/J.TCS.2015.10.017MaRDI QIDQ897901zbMATH OpenOpenAlexFDO

Authors Ran Gu, Xueliang Li, Zhongmei Qin

Publication date 8 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

proper connection numberproper-path coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80)

Abstract: A path in an edge-colored graph is called a proper path if no two adjacent edges of the path are colored the same. For a connected graph $G$, the proper connection number $pc(G)$ of $G$ is defined as the minimum number of colors needed to color its edges, so that every pair of distinct vertices of $G$ is connected by at least one proper path in $G$. In this paper, we show that almost all graphs have the proper connection number 2. More precisely, let $G(n,p)$ denote the Erd"{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$, $pc(G(n,p))le2$ if $pgefraclogn+alpha(n)n$, where $alpha(n)ightarrowinfty$.

Recommendations

• Proper connection with many colors
• Proper connection and size of graphs
• Proper connection number 2, connectivity, and forbidden subgraphs
• Upper bounds of proper connection number of graphs
• Degree sum conditions for graphs to have proper connection number 2.

Cites work

• Almost all regular graphs are hamiltonian
• Graph theory
• Hamiltonian circuits in random graphs
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• On rainbow connection
• On rainbow-k-connectivity of random graphs
• On two Hamilton cycle problems in random graphs
• Proper connection of graphs
• Properties of almost all graphs and complexes
• Rainbow connection in graphs
• Rainbow connection of sparse random graphs
• Random graphs.

Cited in

(26)

• When are random graphs connected
• Conflict-free connections of graphs
• Coloring graphs to produce properly colored walks
• Some upper bounds for the 3-proper index of graphs
• The \(k\)-proper index of graphs
• Graphs with conflict-free connection number two
• Two sufficient conditions for 2-connected graphs to have proper connection number 2
• Conflict-free connection number of random graphs
• Optimal proper connection of graphs
• Hardness results for three kinds of colored connections of graphs
• On the number of alternating paths in random graphs
• The optimal proper connection number of a graph with given independence number
• On the total proper connection of graphs
• Note on directed proper connection number of a random graph
• On two conjectures about the proper connection number of graphs
• Minimum degree condition for proper connection number 2
• scientific article; zbMATH DE number 3923752 (Why is no real title available?)
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• On the (di)graphs with (directed) proper connection number two
• On the (di)graphs with (directed) proper connection number two
• The fine-grained complexity of approximately counting proper connected colorings (extended abstract)
• List proper connection of 2-edge-connected graphs
• Cut-through connections of graphs
• The \((k,\ell )\)-proper index of graphs
• On anti-A-connectivity in plane graphs
• Proper connection number and connected dominating sets

This page was built for publication: Proper connection number of random graphs

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