Proper connection number of random graphs

DOI10.1016/J.TCS.2015.10.017zbMATH Open1331.05194arXiv1505.04646OpenAlexW1799905119MaRDI QIDQ897901FDOQ897901

Ran Gu, Zhongmei Qin, Xueliang Li

Publication date: 8 December 2015

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

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

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

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.

zbMATH Keywords

proper-path coloringproper connection number

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On rainbow connection
• Rainbow connections of graphs: a survey
• Random graphs.
• Rainbow connection in graphs
• Hamiltonian circuits in random graphs
• Almost all regular graphs are hamiltonian
• Proper connection of graphs
• On rainbow-\(k\)-connectivity of random graphs
• On two Hamilton cycle problems in random graphs
• Properties of almost all graphs and complexes
• Rainbow connection of sparse random graphs

Cited In (23)

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

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)