Geodesic
Parity vertex colorings of binomial trees
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 1, pp. 177-180 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

We show for every k ≥ 1 that the binomial tree of order 3k has a vertex-coloring with 2k+1 colors such that every path contains some color odd number of times. This disproves a conjecture from [1] asserting that for every tree T the minimal number of colors in a such coloring of T is at least the vertex ranking number of T minus one.
Keywords: binomial tree, parity coloring, vertex ranking 
@article{DMGT_2012_32_1_a14,
     author = {Gregor, Petr and \v{S}krekovski, Riste},
     title = {Parity vertex colorings of binomial trees},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {177--180},
     year = {2012},
     volume = {32},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a14/}
}
TY  - JOUR
AU  - Gregor, Petr
AU  - Škrekovski, Riste
TI  - Parity vertex colorings of binomial trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 177
EP  - 180
VL  - 32
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a14/
LA  - en
ID  - DMGT_2012_32_1_a14
ER  - 
%0 Journal Article
%A Gregor, Petr
%A Škrekovski, Riste
%T Parity vertex colorings of binomial trees
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 177-180
%V 32
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a14/
%G en
%F DMGT_2012_32_1_a14
Gregor, Petr; Škrekovski, Riste. Parity vertex colorings of binomial trees. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 1, pp. 177-180. http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a14/

[1] P. Borowiecki, K. Budajová, S. Jendrol' and S. Krajči, Parity vertex colouring of graphs, Discuss. Math. Graph Theory 31 (2011) 183-195, doi: 10.7151/dmgt.1537.

[2] D.P. Bunde, K. Milans, D.B. West and H. Wu, Parity and strong parity edge-colorings of graphs, Combinatorica 28 (2008) 625-632, doi: 10.1007/s00493-008-2364-3.

[3] A.A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math. 66 (2001) 211-249, doi: 10.1023/A:1010767517079.