Maximum number of r-edge-colorings such that all copies of Kk are rainbow
dc.contributor.author | Bastos, Antônio Josefran de Oliveira | pt_BR |
dc.contributor.author | Lefmann, Hanno | pt_BR |
dc.contributor.author | Oertel, Andy | pt_BR |
dc.contributor.author | Hoppen, Carlos | pt_BR |
dc.contributor.author | Schmidt, Dionatan Ricardo | pt_BR |
dc.date.accessioned | 2022-08-16T04:46:04Z | pt_BR |
dc.date.issued | 2021 | pt_BR |
dc.identifier.issn | 1877-0509 | pt_BR |
dc.identifier.uri | http://hdl.handle.net/10183/246900 | pt_BR |
dc.description.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 suffices to prove a related stability result. | en |
dc.format.mimetype | application/pdf | pt_BR |
dc.language.iso | eng | pt_BR |
dc.relation.ispartof | Procedia Computer Science. Amsterdam. Vol. 195 (2021), p. 419 - 426 | pt_BR |
dc.rights | Open Access | en |
dc.subject | Edge-colorings | en |
dc.subject | Grafos | pt_BR |
dc.subject | Turán problem | en |
dc.subject | Coloração de arestas | pt_BR |
dc.subject | Arco-iris | pt_BR |
dc.subject | Erdős-Rothschild problem | en |
dc.title | Maximum number of r-edge-colorings such that all copies of Kk are rainbow | pt_BR |
dc.type | Artigo de periódico | pt_BR |
dc.identifier.nrb | 001136292 | pt_BR |
dc.type.origin | Estrangeiro | pt_BR |
Files in this item
This item is licensed under a Creative Commons License
-
Journal Articles (39774)Exact and Earth Sciences (6068)