Monochromatic graph decompositions and monochromatic piercing inspired by anti-Ramsey colorings
Yair Caro, Zsolt Tuza · 2025
Read Monochromatic graph decompositions and monochromatic piercing inspired by anti-Ramsey colorings by Yair Caro, Zsolt Tuza (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-2501-09342.txt.
Description
Yair Caro and Zsolt Tuza closed a trilogy in 2025 on monochromatic graph problems inspired by anti-Ramsey theory. Anti-Ramsey theory, begun in 1975, studies edge colorings of complete graphs that force certain colored patterns. The authors generalize that field through two functions defined for a graph and a family of graphs.
One function gives the fewest colors that force a copy of the target graph whose color classes all lie in the family. The other gives the most colors in a coloring where every copy holds an induced color class from the family. The team develops methods that give tight asymptotic results for many choices of target and family. Readers get tools for piercing and decomposition questions where a single color must do the work.
Catalog record
| CREATOR | Yair Caro, Zsolt Tuza |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 144 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-09342