The 1,2,3-Conjecture (2004?) and the 1,2-Conjecture

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.

[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, .