@article{19859,
  abstract     = {We consider a recently introduced model of color-avoiding percolation (abbreviated CA-percolation) defined as follows. Every edge in a graph G is colored in some of k>=2 colors. Two vertices u and v in G are said to be CA-connected if u and v may be connected using any subset of k-1 colors. CA-connectivity defines an equivalence relation on the vertex set of G whose classes are called CA-components.
We study the component structure of a randomly colored Erdős–Rényi random graph of constant average degree. We distinguish three regimes for the size of the largest component: a supercritical regime, a so-called intermediate regime, and a subcritical regime, in which the largest CA-component has respectively linear, logarithmic, and bounded size. Interestingly, in the subcritical regime, the bound is deterministic and given by the number of colors.},
  author       = {Lichev, Lyuben and Schapira, Bruno},
  issn         = {2644-9463},
  journal      = {Annales Henri Lebesgue},
  pages        = {35--65},
  publisher    = {École normale supérieure de Rennes},
  title        = {{Color-avoiding percolation on the Erdős–Rényi random graph}},
  doi          = {10.5802/ahl.228},
  volume       = {8},
  year         = {2025},
}