zbMATH — the first resource for mathematics

Digraphs are 2-weight choosable. (English) Zbl 1205.05101
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.

05C22 Signed and weighted graphs
05C15 Coloring of graphs and hypergraphs
Full Text: EMIS EuDML