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: (Przybyło-Woźniak; possibly also Kyoshi-Hulgan-Lehel) If each vertex is also given a weight, and the sum at a vertex includes the weight of the vertex, then there is a proper weighting from {1,2}.
Comments: Conjecture 1 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; Reed et al. [R] showed that k=17 suffices. Conjecture 2 is true for 3-colorable graphs, and colors 1 through 11 always suffice for a proper weighting. In fact, colors 1 through 1+⌊χ(G)/2⌋ suffice.
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:
[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ö;
[KLT] Karónski, Michał; Łuczak, Tomasz; Thomason, Andrew;
Edge weights and vertex colours.
J. Combin. Theory Ser. B 91 (2004), no. 1, 151--157.
[R?] Reed, Bruce et al.