Digraphs are $2$-Weight Choosable

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


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. Bartnicki et al. 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.

Full Text: PDF