# Proper Weightings and Lucky Labelings (2008)

Originators: Czerwiński, Grytczuk, and Żelazny    (presented by D.B. West - REGS 2009)

Definitions: A weighting of a graph is an assignment of numbers to some "elements" of a graph, which may be the edges, the vertices, or both (a "total" weighting). In these three cases, a vertex "sees" the weight on its incident edges, its neighbors, and itself plus its incident edges, respectively. The weighting is proper if coloring each vertex with the sum of the weights it sees yields a proper coloring of the graph. The lucky number of a graph is the minimum k such that a proper vertex-weighting exists using weights in {1,...,k}.

Background: The 1,2,3-Conjecture of Karoński, Łuczak, and Thomason [KLT] and the 1,2-Conjecture of Przybyło and Woźniak [PW] were presented in more detail (with history) in REGS 2007. These conjectures state that every graph has a proper edge-weighting with weights in {1,2,3} and a proper total-weighting with weights in {1,2}, respectively. The best current results are that proper edge-weightings exist with weights in {1,2,3,4,5} [KKP] and proper total-weightings exist with weights in {1,2,3} [K].

Conjecture 1: [CGZ] Every graph G has a proper vertex-weighting with weights in {1,...,χ(G)}. That is, the lucky number is always at most the chromatic number. A weaker conjecture is that the lucky number is bounded by a function of the chromatic number.

Comments: Complete graphs show that one cannot guarantee the lucky number to be less than the chromatic number. Czerwiński, Grytczuk, and Żelazny [CGZ] used the Combinatorial Nullstellensatz to prove that every bipartite graph having an orientation with maximum outdegree at most k has a proper vertex weighting chosen from any lists of size at least k+1 at the vertices; hence it has lucky number at most k+1. This proves the conjecture for trees but without an explicit algorithm. Fox and Orlow (REGS 2009) found a simple algorithm to produce lucky labelings for trees. However, it is not known whether the lucky number is bounded for bipartite graphs. [CGZ] also proved that the lucky number of a planar graph is at most 100,280,245,065 (using acyclic colorings); this was later reduced to 1260.

[BGP] considers related problems involving orientations of graphs and weightings of digraphs. Among many other results, they show that every graph has an orientation in which the indegrees of vertices are distinct, and every graph has an orientation in which the values of indegree-outdegree are distinct.

Conjecture 2: (Grytczuk) For every graph and every integer k greater than 1, there is a labeling of the vertices with integers so that the sum of the labels in each closed neighborhood is nonzero modulo k.

Comments: For k=2, Conjecture 2 is equivalent to showing that every graph has an odd dominating set, which is a set containing an odd number of vertices in each closed neighborhood. There is a combinatorial proof of this due to Gallai (see Lovász [Lov]), a proof by linear algebra [Los], and a proof using the Combinatorial Nullstellensatz. Given a graph, a solution valid for any k is also valid for any multiple of k, so it remains only to consider odd k.

References:
[CGZ] S. Czerwiński, J. Grytczuk, and W. Żelazny, Lucky labelings of graphs, Info. Proc. Letters (2009).
[BGP] M. Borwiecki, J. Grytczuk, and M. Pilśniak, Coloring chip configurations on graphs and digraphs, manuscript (2009).
[K] M. Kalkowski, manuscript (2008).
[KKP] M. Kalkowski; M. Karoński; F. Pfender, Vertex-coloring edge-weightings: towards 1-2-3-conjecture, manuscript (2008).
[KLT] Karoński, Michał; Łuczak, Tomasz; Thomason, Andrew; Edge weights and vertex colours. J. Combin. Theory Ser. B 91 (2004), no. 1, 151--157.
[Los] O.P. Lossers, An all-ones problem (solution to problem 10197 proposed by U. Peled. Amer. Math. Monthly 100 (1993), 806-807.
[Lov] Lovász, L. Combinatorial problems and exercises. North-Holland Publishing Co., Amsterdam-New York, 1979, page 289.
[PW] Przybyło, Jakub; Woźniak, Mariusz; 1,2-conjecture, Preprints MD-024 and MD-026, http://www.ii.uj.edu.pl/preMD/index.php .