[{"publisher":"École normale supérieure de Rennes","publication_status":"published","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.","status":"public","date_created":"2025-06-22T22:02:07Z","OA_place":"publisher","author":[{"first_name":"Lyuben","full_name":"Lichev, Lyuben","last_name":"Lichev","id":"9aa8388e-d003-11ee-8458-c4c1d7447977"},{"first_name":"Bruno","full_name":"Schapira, Bruno","last_name":"Schapira"}],"year":"2025","article_processing_charge":"Yes","title":"Color-avoiding percolation on the Erdős–Rényi random graph","oa_version":"Published Version","arxiv":1,"ddc":["510"],"page":"35-65","day":"01","type":"journal_article","scopus_import":"1","language":[{"iso":"eng"}],"date_published":"2025-06-01T00:00:00Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"has_accepted_license":"1","doi":"10.5802/ahl.228","publication_identifier":{"eissn":["2644-9463"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2025-06-23T11:59:22Z","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>","short":"L. Lichev, B. Schapira, Annales Henri Lebesgue 8 (2025) 35–65.","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.","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>.","ista":"Lichev L, Schapira B. 2025. Color-avoiding percolation on the Erdős–Rényi random graph. Annales Henri Lebesgue. 8, 35–65.","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>."},"quality_controlled":"1","OA_type":"gold","article_type":"original","month":"06","file":[{"access_level":"open_access","date_updated":"2025-06-23T11:59:22Z","relation":"main_file","file_name":"2025_AnnalesHenriLebesgue_Lichev.pdf","checksum":"cca22d171b7affa010d17f5e793b0045","creator":"dernst","success":1,"file_size":746588,"date_created":"2025-06-23T11:59:22Z","content_type":"application/pdf","file_id":"19875"}],"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."}],"_id":"19859","intvolume":"         8","publication":"Annales Henri Lebesgue","department":[{"_id":"MaKw"}],"DOAJ_listed":"1","volume":8,"date_updated":"2025-06-23T12:01:36Z","external_id":{"arxiv":["2211.16086 "]},"corr_author":"1","oa":1}]