**Originators:** Michał Karonski, Tomasz Łuczak, and Andrew
Thomason; Jakub Pryzbyło and Mariusz Woźniak
(presented by A. Kostochka - REGS 2007)

**Definitions:** Given a weighting of the edge set of a
graph, let *f(v)* denote the sum of the weights of the edges incident
to *v*, for each *v∈V(G)*. A weighting is *antimagic*
or *irregular* if the resulting vertex weighting *f* is injective,
and the minimum *k* such that this can be done with weights 1 through
*k* is the *irregularity strength* of the
graph. A weaker condition is to require *f(u)≠f(v)* only when
*u* and *v* are adjacent; call such a weighting a
*proper weighting*, since the resulting *f* is a proper coloring.

**Conjecture 1** ([KLT]): Every connected graph with at least
three vertices has a proper weighting from *{1,2,3}*.

**Conjecture 2: **([PW]): If each vertex is also given a
weight (forming a *total weighting*, and the sum at a vertex includes the
weight of the vertex, then there is a proper total weighting from
*{1,2}*.

**Comments:**
The 1,2,3-Conjecture is true for *3*-colorable graphs [KLT]. Regardless
of chromatic number, there is a fixed bound *k* such that colors 1 through
*k* always suffice; [ADMRT] showed that *k=*30 suffices. This was
reduced to 16 in [ABDR] and to 13 in [KLT]. A subsequent breakthrough reduced
the bound to *k=5* (Kalkowski-Karónski--Pfender [KKP]).

This breakthrough was based on a remarkably simple analogous breakthrough for
the 1,2-Conjecture. Przybylo and Wozniak [PW] showed that the 1,2-Conjecture
is true for *3*-colorable graphs, that colors 1 through 11 always
suffice for a proper total weighting, and that colors *1* through
1+⌊*χ(G)/2*⌋ suffice. The breakthrough by
Kalkowski [K] is that every graph has a proper total weighting with vertex
weights in *{1,2}* and edge weights in *{1,2,3}*.

For regular graphs, Conjecture 2 is equivalent to putting a 0,1-labeling on the vertices and edges so that at or incident to adjacent vertices the number of 1s is distinct. In this language, Hulgan and Lehel [HL] proved that the conjecture holds for 4-regular graphs consisting of a 3-regular bipartite graph plus a perfect matching in each part.

Many papers study the minimum number of colors in an ordinary proper
edge-coloring that yields distinct *sets* at adjacent vertices.
This is *adjacent vertex-distinguishing edge-coloring* (see [BGLS]).
By analogy with the relationship between Conjectures 1 and 2, one could seek
the minimum number of colors in a total coloring that yields
distinct *sets* at adjacent vertices (a *total coloring* assigns
colors to vertices and edges so that incident or adjacent vertices or edges
have distinct colors.

**Conjecture 3**:
Every graph *G* has an adjacent vertices-distinguishing total coloring
with at most *Δ(G)+3* colors.

**Comments:**
The Total Coloring Conjecture states that *Δ(G)+2* colors
suffice for a total coloring; Conjecture 3 states that one more color allows
it to distinguish vertices. The bound is sharp for complete graphs with odd
order, but it is not known to be sharp for any other graphs. Hulgan proved
Conjecture 3 for graphs with maximum degree 3.

**References: **

[ADMRT] Addario-Berry, Louigi; Dalal, Ketan; McDiarmid, Colin; Reed,
Bruce A.; Thomason, Andrew. Vertex-colouring edge-weightings. Combinatorica
27 (2007), no. 1, 1--12.

[BGLS] Balister, P. N.; Györi, E.; Lehel, J.; Schelp, R. H.;
Adjacent vertex distinguishing edge-colorings. SIAM J. Discrete Math. 21
(2007), no. 1, 237--250.

[H] Hulgan, Jonathan

[HL] Hulgan, Jonathan; Lehel, Jenö;

[K] M. Kalkowski, manuscript (2008).

[KKP] M. Kalkowski; M. Karónski; F. Pfender,
Vertex-coloring edge-weightings: towards 1-2-3-conjecture, manuscript (2008).

[KLT] Karónski, Michał; Łuczak, Tomasz; Thomason, Andrew;
Edge weights and vertex colours.
J. Combin. Theory Ser. B 91 (2004), no. 1, 151--157.

[PW] Przybylo, Jakub; Wozniak, Mariusz; 1,2-conjecture, Preprint MD-024,
http://www.ii.uj.edu.pl/preMD/index.php .