Maximum number of edge colorings avoiding rainbow copies of $K_4$
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915267981869056 |
|---|---|
| author | Hàn, Hiêp Hoppen, Carlos Müller, Nicolas Moro Schmidt, Dionatan Ricardo |
| author_facet | Hàn, Hiêp Hoppen, Carlos Müller, Nicolas Moro Schmidt, Dionatan Ricardo |
| contents | In this paper we show that for $r\geq 12$ and any sufficiently large $n$-vertex graph $G$ the number of $r$-edge-colorings of $G$ with no rainbow $K_4$ is at most $r^{ex(n,K_4)}$, where $ex(n,K_4)$ denotes the Turán number of $K_4$. Moreover, $G$ attains equality if and only if it is the Turán graph $T_3(n)$.
The bound on the number of colors $r\geq 12$ is best possible. It improves upon a result of H. Lefmann, D.A. Nolibos, and the second author who showed the same result for $r \geq 5434$ and it confirms a conjecture by Gupta, Pehova, Powierski and Staden. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_19244 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Maximum number of edge colorings avoiding rainbow copies of $K_4$ Hàn, Hiêp Hoppen, Carlos Müller, Nicolas Moro Schmidt, Dionatan Ricardo Combinatorics 05C35 G.2.2 In this paper we show that for $r\geq 12$ and any sufficiently large $n$-vertex graph $G$ the number of $r$-edge-colorings of $G$ with no rainbow $K_4$ is at most $r^{ex(n,K_4)}$, where $ex(n,K_4)$ denotes the Turán number of $K_4$. Moreover, $G$ attains equality if and only if it is the Turán graph $T_3(n)$. The bound on the number of colors $r\geq 12$ is best possible. It improves upon a result of H. Lefmann, D.A. Nolibos, and the second author who showed the same result for $r \geq 5434$ and it confirms a conjecture by Gupta, Pehova, Powierski and Staden. |
| title | Maximum number of edge colorings avoiding rainbow copies of $K_4$ |
| topic | Combinatorics 05C35 G.2.2 |
| url | https://arxiv.org/abs/2503.19244 |