Total Weight Choosability of Graphs

Suppose the edges and the vertices of a simple graph $G$ are assigned $k$-element lists of real weights. By choosing a representative of each list, we specify a vertex colouring, where for each vertex its colour is defined as the sum of the weights of its incident edges and the weight of the vertex...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2011-05, Vol.18 (1)
Main Authors: Przybyło, Jakub, Woźniak, Mariusz
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Suppose the edges and the vertices of a simple graph $G$ are assigned $k$-element lists of real weights. By choosing a representative of each list, we specify a vertex colouring, where for each vertex its colour is defined as the sum of the weights of its incident edges and the weight of the vertex itself. How long lists ensures a choice implying a proper vertex colouring for any graph? Is there any finite bound or maybe already lists of length two are sufficient? We prove that $2$-element lists are enough for trees, wheels, unicyclic and complete graphs, while the ones of length $3$ are sufficient for complete bipartite graphs. Our main tool is an algebraic theorem by Alon called Combinatorial Nullstellensatz.
ISSN:1077-8926
1077-8926
DOI:10.37236/599