An extension of the rainbow Erdős-Rothschild problem

DOI10.1016/J.DISC.2021.112443MaRDI QIDQ2032865zbMATH OpenOpenAlexFDO

Authors Carlos Hoppen, Hanno Lefmann, Denilson Nolibos

Publication date 14 June 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.11892

zbMATH Keywords

\((k - 1)\)-partite Turán graphTurán problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Given integers $rgeq2$, $kgeq3$ and $$, and a graph $G$, we consider $r$-edge-colorings of $G$ with no copy of a complete graph $K_k$ on $k$ vertices where $s$ or more colors appear, which are called $mathcal{P}_{k,s}$-free $r$-colorings. We show that, for large $n$ and $rgeq{r}_0(k,s)$, the $(k-1)$-partite Tur'an graph $T_{k-1}(n)$ on $n$ vertices yields the largest number of $mathcal{P}_{k,s}$-free $r$-colorings among all $n$-vertex graphs, and that it is the unique graph with this property.

Recommendations

• A rainbow Erdös-Rothschild problem
• A rainbow Erdős-Rothschild problem
• Rainbow Erdös-Rothschild problem for the Fano plane
• On the rainbow version of a problem of Roth
• A rainbow \(r\)-partite version of the Erdős-Ko-Rado theorem
• An extension of a result of Erdős and Zaremba
• An extension of the Erdős-Tetali theorem
• A rainbow Ramsey analogue of Rado's theorem
• Two extensions of the Erdős-Szekeres problem
• scientific article; zbMATH DE number 887756

Cites work

• A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity
• A rainbow Erdös-Rothschild problem
• A remark on the number of edge colorings of graphs
• Edge colorings of graphs without monochromatic stars
• Edge-colorings avoiding a fixed matching with a prescribed color pattern
• Edge-colorings of graphs avoiding complete graphs with a prescribed coloring
• Edge-colorings of graphs avoiding fixed monochromatic subgraphs with linear Turán number
• scientific article; zbMATH DE number 3487496 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 881297 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• Improved bound on the maximum number of clique-free colorings with two and three colors
• On graphs with a large number of edge-colorings avoiding a rainbow triangle
• Remarks on an edge-coloring problem
• The Erdős–Rothschild problem on edge-colourings with forbidden monochromatic cliques
• The history of degenerate (bipartite) extremal graph problems
• The maximum number of \(K_{3}\)-free and \(K_{4}\)-free edge 4-colorings
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• The number of Gallai k-colorings of complete graphs
• The number of oriantations having no fixed tournament
• The Typical Structure of Gallai Colorings and Their Extremal Graphs

Cited in

(12)

• Monochromatic stars in rainbow \(K_3\)-free and \(S_3^+\)-free colorings
• Further approximations for Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture
• Remarks on an edge-coloring problem
• Edge-colorings of graphs avoiding complete graphs with a prescribed coloring
• Graphs with many edge-colorings such that complete graphs are rainbow
• The maximum number of \(K_{3}\)-free and \(K_{4}\)-free edge 4-colorings
• A rainbow Erdős-Rothschild problem
• A rainbow Erdös-Rothschild problem
• Generalizations of the Ruzsa–Szemerédi and rainbow Turán problems for cliques
• Stability for the Erdős-Rothschild problem
• Exact solutions to the Erdős-Rothschild problem
• Edge-colorings avoiding patterns in a triangle

This page was built for publication: An extension of the rainbow Erdős-Rothschild problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2032865)