Digraphs are 2-weight choosable
type: Item
instance of: scholarly article
title: Digraphs are 2-weight choosable
zbMATH Open document ID: 1205.05101
author: Mahdad Khatirinejad
author: Reza Naserasr
author: Ben Seamone
author: Brett Stevens
author: Mike Newman
published in: The Electronic Journal of Combinatorics
publication date: 2011-02-17T00:00:00Z
full work available at URL: https://eudml.org/doc/228343
full work available at URL: v18i1p21.html
review text: 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.
Mathematics Subject Classification ID: 05C22
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5852471
zbMATH Keywords: edge weighting vertex coloring
zbMATH Keywords: weight colorability
zbMATH Keywords: digraphs
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5852471