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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1595,
author = {Petr Gregor and Riste \v Skrekovski},
title = {Parity vertex colorings of binomial trees},
journal = {Discussiones Mathematicae Graph Theory},
volume = {32},
year = {2012},
pages = {177-180},
zbl = {1255.05081},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1595}
}
Petr Gregor; Riste Škrekovski. Parity vertex colorings of binomial trees. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 177-180. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1595/
[000] [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. | Zbl 1284.05091
[001] [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. | Zbl 1199.05105
[002] [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. | Zbl 0982.05044