2025/04/30 by Bensmail, Julien, Martins, Beatriz, Tang, Chaoliang
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2504.21452
In a recent work, Keusch proved the so-called 1-2-3 Conjecture, raised by Karoński, Łuczak, and Thomason in 2004: for every connected graph different from K2, we can assign labels~1,2,3 to the edges so that no two adjacent vertices are incident to the same sum of labels. Despite this significant result, several problems close to the 1-2-3 Conjecture in spirit remain widely open. In this work, we focus on the so-called 1-2 Conjecture, raised by Przybyło and Woźniak in 2010, which is a counterpart of the 1-2-3 Conjecture where labels~1,2 only can be assigned, and both vertices and edges are labelled. We consider both the 1-2 Conjecture in its original form, where adjacent vertices must be distinguished w.r.t.~their sums of incident labels, and variants for products and multisets. We prove some of these conjectures for graphs with bounded maximum degree (at most~6) and bounded maximum average degree (at most~3), going beyond earlier results of the same sort.