Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Graphs with many edge-colorings such that complete graphs are rainbow

Bastos, Josefran de O. ; Hoppen, Carlos ; Lefmann, Hanno ; Oertel, Andy LU orcid and Schmidt, Dionatan R. (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)
Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
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}},
}