A NOTE ON EDGE WEIGHT CHOOSABILITY OF GRAPHS
Jingcheng Fu, Guanghui Wang, Jianliang Wu, Jin An Xu · Discrete Mathematics Algorithms and Applications · 2013
In 2004, Karoński, Łuczak, and Thomason conjectured that the edges of any connected graph on at least 3 vertices may be weighted from the set {1, 2, 3} so that the vertices are properly colored by the sums of their incident edge weights. Bartnicki, Grytczuk and Niwcyk introduced its list version. Assign to each edge e ∈ E(G) a list of k real numbers, say L(e), and choose a weight w(e) ∈ L(e) for each e ∈ E(G). The resulting function w : E(G) → ⋃e∈E(G) L(e) is called an edge k-list-weighting. Given a graph G, the smallest k such that any assignment of lists of size k to E(G) permits an edge k-list-weighting which is a vertex coloring by sums is denoted by [Formula: see text] and called the edge weight choosability of G. Bartnicki, Grytczuk and Niwcyk conjectured that if G is a nice graph (without a component isomorphic to K2), then [Formula: see text]. There is no known constant K such that [Formula: see text] for any nice graph G. Ben Seamone proved that [Formula: see text] for any nice graph G with maximum degree Δ(G) by using Alon's Combinatorial Nullstellensatz. In this paper, we improve this bound to [Formula: see text].