Um problema de coloração de arestas em grafos evitando um padrão específico em triângulos

Dionatan R. Schmidt, Carlos Hoppen, Hanno Lefmann

Resumo


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.


Palavras-chave


Teoria Extremal de Grafos; Problema de Erdős-Rothschild; Coloração de Arestas

Texto completo:

PDF

Referências


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




DOI: https://doi.org/10.5540/03.2022.009.01.0321

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato