Graphs with many edge-colorings such that complete graphs are rainbow
(2023) In Discrete Applied Mathematics 333. p.151-164- Abstract
We consider a version of the Erdős–Rothschild problem for families of graph patterns. For any fixed k≥3, let r0(k) be the largest integer such that the following holds for all 2≤r≤r0(k) and all sufficiently large n: The Turán graph Tk−1(n) is the unique n-vertex graph G with the maximum number of r-edge-colorings such that the edge set of any copy of Kk in G is rainbow. We use the regularity lemma of Szemerédi and linear programming to obtain a lower bound on the value of r0(k). For a more general family P of patterns of Kk, we also prove that, in order to show that the Turán graph Tk−1(n) maximizes the number of P-free r-edge-colorings over n-vertex graphs, it... (More)
We consider a version of the Erdős–Rothschild problem for families of graph patterns. For any fixed k≥3, let r0(k) be the largest integer such that the following holds for all 2≤r≤r0(k) and all sufficiently large n: The Turán graph Tk−1(n) is the unique n-vertex graph G with the maximum number of r-edge-colorings such that the edge set of any copy of Kk in G is rainbow. We use the regularity lemma of Szemerédi and linear programming to obtain a lower bound on the value of r0(k). For a more general family P of patterns of Kk, we also prove that, in order to show that the Turán graph Tk−1(n) maximizes the number of P-free r-edge-colorings over n-vertex graphs, it suffices to prove a related stability result.
(Less)
- author
- Bastos, Josefran de O. ; Hoppen, Carlos ; Lefmann, Hanno ; Oertel, Andy LU and Schmidt, Dionatan R.
- organization
- publishing date
- 2023
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Erdos–Gallai problem, Linear programing, Rainbow colorings, Regularity lemma
- in
- Discrete Applied Mathematics
- volume
- 333
- pages
- 14 pages
- publisher
- Elsevier
- external identifiers
-
- scopus:85151367531
- ISSN
- 0166-218X
- DOI
- 10.1016/j.dam.2023.03.012
- language
- English
- LU publication?
- yes
- id
- bd4de6b0-d7f7-43ff-954c-8b7a1d60757f
- date added to LUP
- 2023-05-15 14:49:16
- date last changed
- 2023-11-22 18:18:28
@article{bd4de6b0-d7f7-43ff-954c-8b7a1d60757f, abstract = {{<p>We consider a version of the Erdős–Rothschild problem for families of graph patterns. For any fixed k≥3, let r<sub>0</sub>(k) be the largest integer such that the following holds for all 2≤r≤r<sub>0</sub>(k) and all sufficiently large n: The Turán graph T<sub>k−1</sub>(n) is the unique n-vertex graph G with the maximum number of r-edge-colorings such that the edge set of any copy of K<sub>k</sub> in G is rainbow. We use the regularity lemma of Szemerédi and linear programming to obtain a lower bound on the value of r<sub>0</sub>(k). For a more general family P of patterns of K<sub>k</sub>, we also prove that, in order to show that the Turán graph T<sub>k−1</sub>(n) maximizes the number of P-free r-edge-colorings over n-vertex graphs, it suffices to prove a related stability result.</p>}}, author = {{Bastos, Josefran de O. and Hoppen, Carlos and Lefmann, Hanno and Oertel, Andy and Schmidt, Dionatan R.}}, issn = {{0166-218X}}, keywords = {{Erdos–Gallai problem; Linear programing; Rainbow colorings; Regularity lemma}}, language = {{eng}}, pages = {{151--164}}, publisher = {{Elsevier}}, series = {{Discrete Applied Mathematics}}, title = {{Graphs with many edge-colorings such that complete graphs are rainbow}}, url = {{http://dx.doi.org/10.1016/j.dam.2023.03.012}}, doi = {{10.1016/j.dam.2023.03.012}}, volume = {{333}}, year = {{2023}}, }