MathDB

The 1-2-3-Conjecture for graphs

Let GG be a graph without isolated edges. A weighting of the edges is a function ω:E(G)→{1,2,3}\omega:E(G)\to\{1,2,3\}, and the induced vertex weight is

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

The 1-2-3-Conjecture. For every graph GG without isolated edges, there is a weighting ω:E(G)→{1,2,3}\omega:E(G)\to\{1,2,3\} such that the induced vertex weights properly color V(G)V(G).

This conjecture concerns the existence of a three-valued edge weighting distinguishing the weighted degrees of adjacent vertices. It is known for several classes of graphs, while the best general result stated in the source uses weights from {1,2,3,4,5}\{1,2,3,4,5\} rather than {1,2,3}\{1,2,3\}; the conjecture remains open in general.

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 graphs

    Let GG be a graph without isolated edges. A weighting ω:E(G)→{1,2,3}\omega:E(G)\to\{1,2,3\} induces vertex weights

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

    The 1-2-3 Conjecture. There is such a weighting for which the induced vertex weights properly color V(G)V(G).

    This is the graph case of the 1-2-3 problem, asking whether three edge weights always suffice to distinguish the weighted degrees of adjacent vertices. The source provides no resolution status here.

    source: Maciej Kalkowski, Michał Karoński and Florian Pfender, “The 1-2-3 Conjecture for Hypergraphs”, arXiv:1308.0611 (2016).

Sources & referencesView supporting material

Primary source

Florian Pfender, “Total weight choosability in Hypergraphs”, arXiv:1312.6329 (2013).

edge-weightingsgraph-coloringgraph-theorytotal-weighting

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.