Portal de Periódicos da CAPES

Artigo Acesso aberto Produção Nacional

BIBTEX RIS

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

2022; Linguagem: Português

10.5540/03.2022.009.01.0321

2359-0793

Dionatan Ricardo Schmidt, Carlos Hoppen, Hanno Lefmann,

Graph Labeling and Dimension Problems

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.