MathDB

The total 1-2 Conjecture

Let GG be a graph. A total kk-weighting assigns weights from {1,…,k}\{1,\ldots,k\} to every vertex and edge, and χΣt(G)\chi_\Sigma^t(G) is the least kk for which some such weighting properly colours adjacent vertices by the sums of the weight at the vertex and the weights on its incident edges.

Total 1-2 Conjecture. For every graph GG,

χΣt(G)≤2.\chi_\Sigma^t(G)\leq 2.

The conjecture is a total-weighting analogue of the 1-2-3 Conjecture. The source records the best general bound as χΣt(G)≤3\chi_\Sigma^t(G)\leq 3, so the conjecture 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 total 1-2 Conjecture

    Let GG be a connected graph. Assign numbers to both vertices and edges, and define S(v)=f(v)+∑x∈N(v)f(vx)S(v)=f(v)+\sum_{x\in N(v)}f(vx). A decoration is total cool if S(u)≠S(v)S(u)\ne S(v) for every adjacent pair u,vu,v. The total 1-2 Conjecture. Every connected graph has a total cool decoration from the set {1,2}\{1,2\}. This is the natural total analogue of the 1-2-3 Conjecture; the corresponding list version is also open.

    source: Jarosław Grytczuk, “From the 1-2-3 Conjecture to the Riemann Hypothesis”, arXiv:2003.02887 (2020).

Sources & referencesView supporting material

Primary source

Ben Seamone, “The 1-2-3 Conjecture and related problems: a survey”, arXiv:1211.5122 (2012).

graph-coloringgraph-weightingstotal-coloringtotal-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.