MathDB

The 1-2-3-conjecture for vertex-coloring edge weightings

Let GG be a finite simple connected graph with at least three vertices. A vertex-coloring kk-edge weighting of GG is an edge-weighting w:E(G)→{1,2,…,k}w:E(G)\rightarrow\{1,2,\ldots,k\} such that the induced coloring

c(v)=∑e∼vw(e)c(v)=\sum_{e\sim v}w(e)

is a proper vertex coloring. Let μ(G)\mu(G) be the minimum kk for which GG has a vertex-coloring kk-edge weighting.

1-2-3-conjecture. For every connected graph GG with at least three vertices,

μ(G)≤3.\mu(G)\leq 3.

This conjecture asserts that edge weights from {1,2,3}\{1,2,3\} always suffice to distinguish the induced sums at adjacent vertices. The paper states that the conjecture is known to hold for some infinite classes of graphs, but does not establish it 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 vertex-coloring edge-weightings

    A finite, undirected, simple connected graph GG is called nice if it has no component isomorphic to K2K_2. A kk-edge-weighting assigns to every edge ee an integer weight w(e)∈{1,…,k}w(e)\in\{1,\dots,k\}, and induces a color on each vertex vv by

    c(v)=∑v∼ew(e).c(v)=\sum_{v\sim e}w(e).

    The weighting is vertex-coloring if c(u)≠c(v)c(u)\ne c(v) for every edge uvuv of GG. 1-2-3 conjecture. Every nice graph admits a vertex-coloring 3-edge-weighting. This conjecture asks whether weights from {1,2,3}\{1,2,3\} always suffice to distinguish the induced sums at adjacent vertices; the source presents it as the central conjecture motivating the study of vertex-coloring edge-weightings.

    source: Hongliang Lu, Qinglin Yu and Cun-Quan Zhang, “Vertex-Coloring 2-Edge-Weighting of Graphs”, arXiv:1007.1505 (2010).

Sources & referencesView supporting material

Primary source

Akbar Davoodi and Behnaz Omoomi, “On the 1-2-3-conjecture”, arXiv:1205.3266 (2012).

edge-weightingsgraph-coloring

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.