A framework for the generalised Erdős-Rothschild problem and a resolution of the dichromatic triangle case
Pranshu Gupta ∗, Yani Pehova †, Emil Powierski ‡, Katherine Staden § · 2025
Read A framework for the generalised Erdős-Rothschild problem and a resolution of the dichromatic triangle case by Pranshu Gupta ∗, Yani Pehova †, Emil Powierski ‡, Katherine Staden § (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-12291.txt.
Description
Pranshu Gupta and co-authors develop a 2025 framework for a broad form of the Erdős-Rothschild problem in graph coloring. The classic problem asks how many edge colorings a graph can have while avoiding a single color copy of a complete graph. Their version forbids a whole family of coloring patterns, not just the single color one.
Such problems often split: for some numbers of colors a plain complete split graph is best, and for others the best graph is harder to find. The authors extend an older framework to the general case and solve two pattern families in full for large graphs. Their results give whole families of best graphs, a first of that kind, and show every best graph for non single color patterns has a complete split form. The work grows out of earlier studies by several named research groups.
Catalog record
| CREATOR | Pranshu Gupta ∗, Yani Pehova †, Emil Powierski ‡, Katherine Staden § |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 195 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-12291