Um problema de coloração de arestas em grafos evitando um padrão específico em triângulos
DOI:
https://doi.org/10.5540/03.2022.009.01.0321Keywords:
Teoria Extremal de Grafos, Problema de Erdős-Rothschild, Coloração de ArestasAbstract
Vamos considerar uma versão multicolorida de um problema originalmente proposto por Erdős e Rothschild. Para inteiros positivos n e r, procuramos por grafos de n vértices que admitem o número máximo de r-colorações, sem conter triângulos em que o padrão de coloração seja de duas arestas com a mesma cor, e a outra aresta com cor diferente. Hoppen e Lefmann [4] conjecturaram que a seguinte propriedade é válida para todo 2 ≤ r ≤ 26, e provaram-na para 2 ≤ r ≤ 12. Para n suficientemente grande, o grafo bipartido completo balanceado com n vértices produz o maior número de tais colorações. Nesse artigo, demonstramos essa conjectura.
Downloads
References
J. Balogh e L. Li. “The Typical Structure of Gallai Colorings and Their Extremal Graphs”. Em: SIAM Journal on Discrete Mathematics 33.4 (2019), pp. 2416–2443. doi: 10.1137/ 19M1253344.
H. Lefmann C. Hoppen e K. Odermann. “A rainbow Erdős-Rothschild problem”. Em: SIAM Journal of Discrete Mathematics 31 (2017), pp. 2647–2674. doi: 10.1016/j.endm.2015. 06.066.
H. Lefmann C. Hoppen e K. Odermann. “On graphs with a large number of edge-colorings avoiding a rainbow triangle”. Em: European J. of Combinatorics 66 (2017), pp. 168–190. doi: 10.1016/j.ejc.2017.06.022.
C. Hoppen e H. Lefmann. “Remarks on an Edge-coloring Problem”. Em: Electronic Notes in Theoretical Computer Science 346 (2019), pp. 511–521. issn: 1571-0661.
P. Keevash J. Balogh e B. Sudakov. “The Number of Edge Colorings With No Monochromatic Cliques”. Em: Journal of the London Mathematical Society 70 (2003). doi: 10.1112/ S0024610704005563.
F. Botler J. Corsten A. Dankovics N. Frankl H. Han A. Jimèmnez e J. Skokan. “Maximum number of triangle-free edge colourings with five and six colours”. Em: Acta Math. Univ. Comenianae LXXXVIII.3 (2019), pp. 495–499. issn: 08629544.
J. O. Bastos H. Lefmann C. Hoppen A. Oertel e D. R. Schmidt. “Maximum number of r-edgecolorings such that all copies of Kk are rainbow”. Em: Procedia Computer Science 195.4 (2021), pp. 419–426.
O. Pikhurko e Z. B. Yilma. “The maximum number of K3-free and K4-free edge 4-colorings”. Em: J. Lond. Math. Soc. 85 (2012), pp. 593–615. doi: 10.1112/jlms/jdr031.
R. Yuster. “The number of edge colorings with no monochromatic triangle”. Em: J. Graph Theory 21 (1996), pp. 441–452. doi: 10.1002/(SICI)1097-0118(199604)21:43.0.CO;2-I
