2021/07/01 by Chang, Jing-zhi, Yang, Chao, Yin, Zhi-xiang +1
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2107.00424
The 1-2-3 Conjecture, posed by Karoński, Łuczak and Thomason, asked whether every connected graph G different from K2 can be 3-edge-weighted so that every two adjacent vertices of G get distinct sums of incident weights. The 1-2 Conjecture states that if vertices also receive colors and the vertex color is added to the sum of its incident edges, then adjacent vertices can be distinguished using only \ 1,2\. In this paper we confirm 1-2 Conjecture for 3-regular graphs. Meanwhile, we show that every 3-regular graph can achieve a neighbor sum distinguishing edge coloring by using 4 colors, which answers 1-2-3 Conjecture positively.