The 1-2-3 Conjecture almost holds for regular graphs

2018/09/27 by Przybyło, Jakub · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1809.10761

Abstract

The well-known 1-2-3 Conjecture asserts that the edges of every graph without isolated edges can be weighted with 1, 2 and 3 so that adjacent vertices receive distinct weighted degrees. This is open in general, while it is known to be possible from the weight set \1,2,3,4,5\. We show that for regular graphs it is sufficient to use weights 1, 2, 3, 4. Moreover, we prove the conjecture to hold for every d-regular graph with d≥ 10⁸.

Cited by

• Every graph is uniform-span (2,2)-choosable: Beyond the 1-2 conjecture

Related

• A note on 1-2-3 and 1-2 Conjectures for 3-regular graphs
• The 1-2-3 Conjecture holds for graphs with large enough minimum degree
• Decomposability of graphs into subgraphs fulfilling the 1-2-3 Conjecture
• On the Standard (2,2)-Conjecture
• The 1-2-3 Conjecture and related problems: a survey