Uma 18-coloração localmente irregular de grafos
Palestra
Resumo
Um grafo é localmente irregular se os vértices extremos de cada aresta tiverem graus distintos. Uma coloração de arestas localmente irregular de um grafo G é uma coloração de arestas, não necessariamente própria, na qual cada classe de cor induz um grafo localmente irregular. Equivalentemente, é uma decomposição de arestas de G em grafos localmente irregulares. Um grafo que admite tal decomposição é decomponível, e o menor número possível de classes é seu índice cromático localmente irregular. Bensmail, Merker e Thomassen, em 2017, obtiveram o primeiro limite absoluto, ou seja, 328, para todos os grafos decomponíveis. Luzar, Przybylo e Sotak, em 2018, reduziram o limite geral para 220. Nesse seminário, mostrarei nosso resultado que melhora o limite superior geral de 220 para 18.
Este é um trabalho conjunto com Vinicius Fernandes dos Santos, Guilherme Oliveira Mota e Maycon Sambinelli.
Materiais