On weight choosability and additive choosability numbers of graphs
Ben Seamone · arXiv (Cornell University) · 2012
In 2004, Karonski, Luczak, 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 coloured by the sums of their incident edge weights. A subsequent conjecture by Przybylo and Wozniak (2010) states that weights from {1,2} suffice if one also weights the vertices of the graph. Bartnicki, Grytczuk and Niwcyk (2009), Przybylo and Wozniak (2011), and Wong, Yang and Zhu (2010) introduced list variations of these weightings. In this paper, Alon's Combinatorial Nullstellensatz is used to prove the first known bounds on the list sizes required to ensure a colouring by sums exists for edge weightings and total weightings. Some constructive results on list variation of additive colourings, a concept introduced by Czerwinski, Grytczuk, and Zelazny (2009), are also presented.