MathDB

The 1-2-3 Conjecture for vertex-colouring edge weightings

Let G=(V,E)G=(V,E) be a connected graph with at least two edges. A 33-weighting of GG is a mapping ω:E→{1,2,3}\omega:E\to\{1,2,3\}, and it is vertex-colouring if the weighted degree sω(v)=∑e∈E(v)ω(e)s_\omega(v)=\sum_{e\in E(v)}\omega(e) gives distinct values to the endpoints of every edge. 1-2-3 Conjecture. Every connected graph with at least two edges admits a vertex-colouring 33-weighting. This is the central 1-2-3 Conjecture, introduced by Karoński, Łuczak and Thomason. The paper proves the conjecture for graphs whose minimum degree is sufficiently large relative to the logarithm of their maximum degree, while the general case remains open.

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. The 1-2-3 Conjecture for vertex-colouring edge weightings

    Let G=(V,E)G=(V,E) be a graph without isolated edges. An edge 33-weighting is a map ω:E→{1,2,3}\omega:E\to\{1,2,3\}, with weighted degree

    σω(v):=∑u∈N(v)ω(uv)\sigma_\omega(v):=\sum_{u\in N(v)}\omega(uv)

    at each vertex vv. The weighting is vertex-colouring if σω(u)≠σω(v)\sigma_\omega(u)\neq\sigma_\omega(v) for every edge uv∈Euv\in E. 1-2-3 Conjecture. Every graph without isolated edges admits a vertex-colouring edge 33-weighting. This is open in general, while it is known to be possible from the weight set {1,2,3,4,5}\{1,2,3,4,5\}.

    source: Jakub Przybyło, “The 1-2-3 Conjecture almost holds for regular graphs”, arXiv:1809.10761 (2019).

Sources & referencesView supporting material

Primary source

Jakub Przybyło, “The 1-2-3 Conjecture holds for graphs with large enough minimum degree”, arXiv:2003.13139 (2020).

graph-colouringgraph-theorygraph-weightingsvertex-colouring

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.