Discussiones Mathematicae Graph Theory 32(1) (2012) 177-180
doi: 10.7151/dmgt.1595

[BIBTex] [PDF] [PS]

Parity Vertex Colorings of Binomial Trees

Petr Gregor

Department of Theoretical Computer Science and Math. Logic
Charles University
Malostranské nám. 25, 118 00 Prague, Czech Republic

Riste Škrekovski

Department of Mathematics
University of Ljubljana
Jadranska 21, 1000 Ljubljana, Slovenia


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

2010 Mathematics Subject Classification: 05C15, 05C05, 05C90, 68R10.


[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.

Received 25 October 2010
Revised 10 February 2011
Accepted 10 February 2011