Show simple item record

dc.contributor.authorBastos, Antônio Josefran de Oliveirapt_BR
dc.contributor.authorLefmann, Hannopt_BR
dc.contributor.authorOertel, Andypt_BR
dc.contributor.authorHoppen, Carlospt_BR
dc.contributor.authorSchmidt, Dionatan Ricardopt_BR
dc.date.accessioned2022-08-16T04:46:04Zpt_BR
dc.date.issued2021pt_BR
dc.identifier.issn1877-0509pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/246900pt_BR
dc.description.abstractWe 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.mimetypeapplication/pdfpt_BR
dc.language.isoengpt_BR
dc.relation.ispartofProcedia Computer Science. Amsterdam. Vol. 195 (2021), p. 419 - 426pt_BR
dc.rightsOpen Accessen
dc.subjectEdge-coloringsen
dc.subjectGrafospt_BR
dc.subjectTurán problemen
dc.subjectColoração de arestaspt_BR
dc.subjectArco-irispt_BR
dc.subjectErdős-Rothschild problemen
dc.titleMaximum number of r-edge-colorings such that all copies of Kk are rainbowpt_BR
dc.typeArtigo de periódicopt_BR
dc.identifier.nrb001136292pt_BR
dc.type.originEstrangeiropt_BR


Files in this item

Thumbnail
   

This item is licensed under a Creative Commons License

Show simple item record