---
DOAJ_listed: '1'
OA_place: publisher
OA_type: gold
_id: '19859'
abstract:
- lang: eng
  text: "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.\r\nWe
    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."
acknowledgement: "We thank Dieter Mitsche for enlightening discussions, Balázs Ráth
  for a number of comments\r\nand corrections on a first version of this paper, and
  an anonymous referee for several useful remarks."
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Lyuben
  full_name: Lichev, Lyuben
  id: 9aa8388e-d003-11ee-8458-c4c1d7447977
  last_name: Lichev
- first_name: Bruno
  full_name: Schapira, Bruno
  last_name: Schapira
citation:
  ama: Lichev L, Schapira B. Color-avoiding percolation on the Erdős–Rényi random
    graph. <i>Annales Henri Lebesgue</i>. 2025;8:35-65. doi:<a href="https://doi.org/10.5802/ahl.228">10.5802/ahl.228</a>
  apa: Lichev, L., &#38; Schapira, B. (2025). Color-avoiding percolation on the Erdős–Rényi
    random graph. <i>Annales Henri Lebesgue</i>. École normale supérieure de Rennes.
    <a href="https://doi.org/10.5802/ahl.228">https://doi.org/10.5802/ahl.228</a>
  chicago: Lichev, Lyuben, and Bruno Schapira. “Color-Avoiding Percolation on the
    Erdős–Rényi Random Graph.” <i>Annales Henri Lebesgue</i>. École normale supérieure
    de Rennes, 2025. <a href="https://doi.org/10.5802/ahl.228">https://doi.org/10.5802/ahl.228</a>.
  ieee: L. Lichev and B. Schapira, “Color-avoiding percolation on the Erdős–Rényi
    random graph,” <i>Annales Henri Lebesgue</i>, vol. 8. École normale supérieure
    de Rennes, pp. 35–65, 2025.
  ista: Lichev L, Schapira B. 2025. Color-avoiding percolation on the Erdős–Rényi
    random graph. Annales Henri Lebesgue. 8, 35–65.
  mla: Lichev, Lyuben, and Bruno Schapira. “Color-Avoiding Percolation on the Erdős–Rényi
    Random Graph.” <i>Annales Henri Lebesgue</i>, vol. 8, École normale supérieure
    de Rennes, 2025, pp. 35–65, doi:<a href="https://doi.org/10.5802/ahl.228">10.5802/ahl.228</a>.
  short: L. Lichev, B. Schapira, Annales Henri Lebesgue 8 (2025) 35–65.
corr_author: '1'
date_created: 2025-06-22T22:02:07Z
date_published: 2025-06-01T00:00:00Z
date_updated: 2025-06-23T12:01:36Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.5802/ahl.228
external_id:
  arxiv:
  - '2211.16086 '
file:
- access_level: open_access
  checksum: cca22d171b7affa010d17f5e793b0045
  content_type: application/pdf
  creator: dernst
  date_created: 2025-06-23T11:59:22Z
  date_updated: 2025-06-23T11:59:22Z
  file_id: '19875'
  file_name: 2025_AnnalesHenriLebesgue_Lichev.pdf
  file_size: 746588
  relation: main_file
  success: 1
file_date_updated: 2025-06-23T11:59:22Z
has_accepted_license: '1'
intvolume: '         8'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 35-65
publication: Annales Henri Lebesgue
publication_identifier:
  eissn:
  - 2644-9463
publication_status: published
publisher: École normale supérieure de Rennes
quality_controlled: '1'
scopus_import: '1'
status: public
title: Color-avoiding percolation on the Erdős–Rényi random graph
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8
year: '2025'
...