Originators: Tsai-Lien Wong and Xuding Zhu (presented by Kyle Jao - REGS 2011)
Definitions: For a vertex v in a graph G. let Γ(v) denote the set of edges incident to v. A total-weighting of G is a map f that assigns each vertex and each edge of G a number as its weight. Such a weighting is proper if the vertex coloring φf defined by φf(v)=f(v)+∑e∈Γ(v)f(e) is proper. An edge-weighting of G can be viewed as a total-weighting with f(v)=0 for all v∈V(G). A (k,k')-total list assignment L for G is a map that assigns each vertex a set of k numbers and each edge a set of k' numbers. The graph G is (k,k')-weight-choosable if for every (k,k')-total list assignment, a proper total weighting can be chosen from the lists.
Background: Karónski, Łuczak and Thomason [KLT] conjectured that every graph without isolated edges has a proper edge-weighting using weights in {1,2,3}; this is known as the 1,2,3-Conjecture. Przybyło and Wozniak [PW1,PW2] conjectured that every graph has a proper total-weighting using weights in {1,2}; this is known as the 1,2-Conjecture. These two conjectures were presented in REGS 2010.
Conjecture 1: ([WZ]) Every graph is (2,2)-weight-choosable. Every graph without isolated edges is (1,3)-weight-choosable.
Comments: A (1,3)-total list assignment may assign list {0} to every vertex. Thus (1,3)-weight-choosability is stronger than "3-edge-weight-choosability" (assigning lists of size 3 as potential edge weights), which in turn is stronger than the 1,2,3-Conjecture. Bartnicki, Grytczuk and Niwczyk [BGN] conjectured that every graph without isolated edges is 3-edge-weight-choosable; they proved this for complete graphs, complete bipartite graphs, and others. In fact, their argument proved that these graphs are (1,3)-weight-choosable. This suggests Conjecture 1.
We now drop the word "weight" and simply write (k,k')-choosable. To further motivate the study of (k,k')-choosability, note that a (k,1)-total list assignment may assign list {0} to every edge, and hence every (k,1)-weight-choosable graph is k-choosable. Thus (k,k')-choosability generalizes the notion of k-choosability. Since larger lists don't hurt, every (k,k')-choosable graph is (k,k'+1)-choosable and (k+1,k')-choosable. Thus the following is weaker than Conjecture 1.
Conjecture 2: For some (k,k'), every graph is (k,k')-choosable.
Comments: Conjecture 1 is sharp, since some graphs are not (1,2)-choosable. For example, no proper total-weightings can be chosen on a complete graph when the vertex lists are all {0} and the edge lists are all {0,1}, since every graph has two vertices with the same degree. However, [BGN] showed that complete graphs are (1,3)-choosable, as are complete bipartite graphs and trees. Wong and Zhu [WZ] proved that complete graphs, trees, and generalized theta graphs are (2,2)-choosable, and another special class of graphs is (1,3)-choosable. In [WYZ], it was proved that Kn,m,1,...,1 is (2,2)-choosable, and complete bipartite graphs with at least three vertices are (1,2)-choosable.
References:
[KLT] M. Karónski, T. Łuczak and A. Thomason,
Edge weights and vertex colours, J. Combin. Theory Ser. B 91 (2004), no. 1, 151--157.
[PW1] J. Przybyło and M. Wozniak, 1,2-conjecture, preprint, 2007
[PW2] J. Przybyło and M. Wozniak, 1,2-conjecture II, preprint, 2007
[BGN] T. Bartnicki, J. Grytczuk and S. Niwczyk, Weight choosability of graphs,
J. Graph Theory 60 (2009), no. 3, 242?V256.
[WZ] T.-L. Wong and X. Zhu,
Total weight choosability of graphs, preprint, 2008.
[WYZ] T.-L. Wong, D. Yang and X. Zhu, List total weighting of graphs, preprint, 2009.