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

CREATORPranshu Gupta ∗, Yani Pehova †, Emil Powierski ‡, Katherine Staden §
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE195 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-12291

Browse the full library · About the Tower of Babel