Geodesic
Total weight choosability of graphs
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/599
Classification : 05C78
Mots-clés : graph labelling, neighbour distinguishing total weighting, total list weighting, vertex colouring 
@article{10_37236_599,
     author = {Jakub Przyby{\l}o and Mariusz Wo\'zniak},
     title = {Total weight choosability of graphs},
     journal = {The electronic journal of combinatorics},
     year = {2011},
     volume = {18},
     number = {1},
     doi = {10.37236/599},
     zbl = {1217.05202},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/599/}
}
TY  - JOUR
AU  - Jakub Przybyło
AU  - Mariusz Woźniak
TI  - Total weight choosability of graphs
JO  - The electronic journal of combinatorics
PY  - 2011
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/599/
DO  - 10.37236/599
ID  - 10_37236_599
ER  - 
%0 Journal Article
%A Jakub Przybyło
%A Mariusz Woźniak
%T Total weight choosability of graphs
%J The electronic journal of combinatorics
%D 2011
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/599/
%R 10.37236/599
%F 10_37236_599
Jakub Przybyło; Mariusz Woźniak. Total weight choosability of graphs. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/599

Cité par Sources :