Digraphs are 2-weight choosable. (English) Zbl 1205.05101

Khatirinejad, Mahdad; Naserasr, Reza; Newman, Mike; Seamone, Ben; Stevens, Brett

Electron. J. Comb. 18, No. 1, Research Paper P21, 4 p. (2011).

Summary: An edge-weighting vertex colouring of a graph is an edge-weight assignment such that the accumulated weights at the vertices yield a proper vertex colouring. If such an assignment from a set \(S\) exists, we say the graph is \(S\)-weight colourable.
We consider the \(S\)-weight colourability of digraphs by defining the accumulated weight at a vertex to be the sum of the inbound weights minus the sum of the outbound weights. T. Bartnicki, J. Grytczuk, and S. Niwczyk [“Weight choosability of graphs,” J. Graph Theory 60, No. 3, 242–256 (2009; Zbl 1210.05138)] showed that every digraph is \(S\)-weight colourable for any set \(S\) of size 2 and asked whether one could show the same result using an algebraic approach. Using the Combinatorial Nullstellensatz and a classical theorem of Schur, we provide such a solution.

MSC:

05C22	Signed and weighted graphs
05C15	Coloring of graphs and hypergraphs

Keywords:

edge weighting vertex coloring; weight colorability; digraphs