Rotulação de arestas semiforte em grafos com grau máximo elevado - Gonzaga, Luis G. S.; Campos, Christiane N. (Anais do Encontro de Teoria da Computação (ETC); 2026: Anais do XI Encontro de Teoria da Computação, 2026)
Uma rotulação de arestas semiforte atribui rótulos às arestas de um grafo de modo que a soma dos rótulos das arestas incidentes em cada vértice resulte em uma coloração própria. A Conjectura 1, 2, 3 (Karoński, Łuczak e Thomason) afirma que todo grafo sem arestas isoladas admite uma rotulação de arestas semiforte com rótulos em {1, 2, 3}. Embora recentemente provada, a construção eficiente de tais rotulações permanece um problema aberto. Neste trabalho, apresentamos um algoritmo em tempo polinomial para obter rotulações de arestas semifortes em grafos com grau máximo pelo menos n− 2.