Color-avoiding percolation of random graphs: between the subcritical and the intermediate regime

DOI10.1016/J.DISC.2023.113713zbMATH Open1526.05125arXiv2301.09910OpenAlexW4387387432MaRDI QIDQ6080191FDOQ6080191

Authors: Lyuben Lichev 

Publication date: 30 October 2023

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

Abstract: Fix a graph $G$ in which every edge is colored in some of $kge2$ colors. Two vertices $u$ and $v$ are CA-connected if $u$ and $v$ may be connected using any subset of $k-1$ colors. CA-connectivity is an equivalence relation dividing the vertex set into classes called CA-components. In two recent papers, R'ath, Varga, Fekete, and Molontay, and Lichev and Schapira studied the size of the largest CA-component in a randomly colored random graph. The second of these works distinguished and studied three regimes (supercritical, intermediate, and subcritical) in which the largest CA-component has respectively linear, logarithmic, and bounded size. In this short note, we describe the phase transition between the intermediate and the subcritical regime.

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

Recommendations

• Color-avoiding percolation and branching processes
• Coloring the edges of a random graph without a monochromatic giant component
• Critical subgraphs of a random graph
• On the complexity of color-avoiding site and bond percolation
• Critical percolation on random regular graphs

zbMATH Keywords

phase transitiongiant componentErdős-Rényi random graphCA-percolation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Discrete-time Markov processes on general state spaces (60J05)

Cites Work

• Component behavior near the critical point of the random graph process
• The Evolution of Random Graphs
• Introduction to Random Graphs

Cited In (2)

• Color-avoiding percolation and branching processes
• Color-avoiding connected spanning subgraphs with minimum number of edges

This page was built for publication: Color-avoiding percolation of random graphs: between the subcritical and the intermediate regime

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