A 1-2-3-4 result for the 1-2-3 Conjecture in 5-regular graphs

Julien Bensmail (1)

1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications

The 1-2-3 Conjecture, posed by Karoński, Łuczak and Thomason, asks 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. Towards that conjecture, the best-known result to date is due to Kalkowski, Karoński and Pfender, who proved that it holds when relaxed to 5-edge-weightings. Their proof builds upon a weighting algorithm designed by Kalkowski for a total version of the problem. In this work, we present new mechanisms for using Kalkowski's algorithm in the context of the 1-2-3 Conjecture. As a main result we prove that every 5-regular graph admits a 4-edge-weighting that permits to distinguish its adjacent vertices via their incident sums.

Keywords: 1-2-3 Conjecture; four weights; 5-regular graphs

Domains: Discrete Mathematics [cs.DM]

Julien Bensmail. A 1-2-3-4 result for the 1-2-3 Conjecture in 5-regular graphs. 2017. ⟨hal-01509365v1⟩