Digraphs are 2-weight choosable (Q625384)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Digraphs are 2-weight choosable |
scientific article |
Statements
Digraphs are 2-weight choosable (English)
0 references
17 February 2011
0 references
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. \textit{T. Bartnicki}, \textit{J. Grytczuk}, and \textit{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.
0 references
edge weighting vertex coloring
0 references
weight colorability
0 references
digraphs
0 references