Paper detail

The 1-2-3 Conjecture holds for graphs with large enough minimum degree

A simple graph more often than not contains adjacent vertices with equal degrees. This in particular holds for all pairs of neighbours in regular graphs, while a lot such pairs can be expected e.g. in many random models. Is there a universal constant $K$, say $K=3$, such that one may always dispose of such pairs from any given connected graph with at least three vertices by blowing its selected edges into at most $K$ parallel edges? This question was first posed in 2004 by Karoński, Łuczak and Thomason, who equivalently asked if one may assign weights $1,2,3$ to the edges of every such graph so that adjacent vertices receive distinct weighted degrees - the sums of their incident weights. This basic problem is commonly referred to as the 1-2-3 Conjecture nowadays, and has been addressed in multiple papers. Thus far it is known that weights $1,2,3,4,5$ are sufficient [J. Combin. Theory Ser. B 100 (2010) 347-349]. We show that this conjecture holds if only the minimum degree $δ$ of a graph is large enough, i.e. when $δ= Ω(\logΔ)$, where $Δ$ denotes the maximum degree of the graph. The principle idea behind our probabilistic proof relies on associating random variables with a special and carefully designed distribution to most of the vertices of a given graph, and then choosing weights for major part of the edges depending on the values of these variables in a deterministic or random manner.