Rotulação de arestas semiforte em grafos com grau máximo elevado

• Luis G. S. Gonzaga Unicamp
• Christiane N. Campos Unicamp

DOI: https://doi.org/10.5753/etc.2026.22122

Resumo

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.

Referências

Addario-Berry, L., Dalal, K., McDiarmid, C., Reed, B. A., and Thomason, A. (2007). Vertex-colouring edge-weightings. Combinatorica, 27(1):1–12.

Addario-Berry, L., Dalal, K., and Reed, B. A. (2008). Degree constrained subgraphs. Discrete Applied Mathematics, 156(7):1168–1174.

Dudek, A. and Wajc, D. (2011). On the complexity of vertex-coloring edge-weightings. Discrete Mathematics and Theoretical Computer Science, 13(3):45–50.

Kalkowski, M., Karonski, M., and Pfender, F. (2009). Vertex colouring edge weightings with integer weights at most 6. In Rostock. Math. Kolloq, volume 64, pages 39–43. Citeseer.

Kalkowski, M., Karoński, M., and Pfender, F. (2010). Vertex-coloring edge-weightings: towards the 1-2-3-conjecture. Journal of Combinatorial Theory, Series B, 100(3):347–349.

Karoński, M., Łuczak, T., and Thomason, A. (2004). Edge weights and vertex colours. Journal of Combinatorial Theory Series B, 91(1):151–157.

Keusch, R. (2024). A solution to the 1-2-3 conjecture. Journal of Combinatorial Theory, Series B, 166:183–202.

Wang, T. and Yu, Q. (2008). On vertex-coloring 13-edge-weighting. Frontiers of Mathematics in China, 3(4):581–587.