{
  "id": "2211.16086",
  "version": "v1",
  "published": "2022-11-29T10:52:44.000Z",
  "updated": "2022-11-29T10:52:44.000Z",
  "title": "Color-avoiding percolation on the Erdős-Rényi random graph",
  "authors": [
    "Lyuben Lichev",
    "Bruno Schapira"
  ],
  "comment": "23 pages, 1 figure",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We consider a recently introduced model of color-avoiding percolation defined as follows. Every edge in a graph $G$ is colored in some of $k\\ge 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\\H{o}s-R\\'enyi 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-11-29T10:52:44.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "erdős-rényi random graph",
      "color-avoiding percolation",
      "subcritical regime",
      "constant average degree",
      "intermediate regime"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}