IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 49 (2011), 1146
ISSN 2232-2094
PARITY VERTEX COLORINGS OF BINOMIAL TREES
Petr Gregor Riste Skrekovski
Ljubljana, March 14, 2011
VD
£ co co
CO CD
Parity vertex colorings of binomial trees
Petr Gregor a and Riste Skrekovski b
$H
March 11, 2011
a Department of Theoretical Computer Science, Charles University, Malostranske nam. 25, 118 00 Prague, Czech Republic Email: gregor@ktiml.mff.cuni.cz Department of Mathematics, University of Ljubljana, Jadranska 21, 1000 Ljubljana, Slovenia. Email: skrekovski@gmail.com
Keywords: binomial tree, parity coloring, vertex ranking
2010 Mathematics Subject Classification: 05C15, 05C05, 05C90, 68R10
Abstract
CO
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.
1 Introduction
A parity vertex coloring of a graph G is a vertex coloring such that each path in G contains some color odd number of times. For a study of parity vertex and (similarly defined) edge colorings, the reader is referred to [1,2]. A vertex ranking of G is a proper vertex coloring by a linearly ordered set of colors such that every path between vertices of the same color contains some vertex of a higher color. The minimum numbers of colors in a parity vertex coloring and a vertex ranking of G are denoted by XP(G) and Xr(G), respectively.
Clearly, every vertex ranking is also parity vertex coloring, so XP(G) < Xr (G) for every graph G. Borowiecki, Budajova, Jendrol', and Krajci [1] conjectured that for trees these parameters behave almost the same.
Conjecture 1. For every tree T it holds xr (T) — XP(T) < 1.
A
o u
VD
0 o
1
CO
£ co co
m
CD
$H
CD
m
u
a
CD U
b \ b
a \ c
b
J
(a)
(b)
Figure 1: (a) The coloring g(a,b,c) of B3, (b) the coloring of two subtrees B3(u) and B3(v) with uv £ E(B3k).
In this note we show that the above conjecture is false for every binominal tree of order n > 5. A binomial tree Bn of order n > 0 is a rooted tree defined recursively. B0 = K1 with the only vertex as its root. The binomial tree Bn for n > 1 is obtained by taking two disjoint copies of Bn-\ and joining their roots by an edge, then taking the root of the second copy to be the root of Bn.
Binomial trees have been under consideration also in other areas. For example, Bn is a spanning tree of the n-dimensional hypercube Qn that has been conjectured [3] to have the minimum average congestion among all spanning trees of Qn. In [1] it was shown, in our notation, that \r(Bn) = n + 1 for all n > 0.
We show that xP(B3k) < 2k +1 for every k > 1, which hence disproves the above conjecture. More precisely, for the purpose of induction we prove a stronger statement in the below theorem. Let us say that a color c on a vertex-colored path P is
•	inner, if c does not appear on the endvertices of P,
•	single, if c appears exactly once on P.
Moreover, we say that a vertex of Bn is even (resp. odd) if its distance to the root is even (resp. odd).
Theorem 2. For every k > 1 the binomial tree B3k has a parity vertex coloring with 2k +1 colors .such that every path of length at least 2 has an inner single color.
Proof. For k = 1 we define the coloring f : V(B3) ^ {1, 2, 3} by f = g(i,2,3) where g(a,b,c) is defined on Figure 1(a). Observe that f satisfies the statement. In what follows, we assume k > 2.
The binomial tree B3k+3 can be viewed as B3k with a copy of B3 hanged on each vertex. See Figure 2 for an illustration. For a vertex v £ V(B3k), let us denote the copy of B3 hanged on v by B3(v). Let f' be the coloring of B3k with colors {1, 2,..., 2k + 1} obtained by induction and let i = 2k + 2, j = 2k + 3 be the new colors. We define the coloring
a
c
b
J
A
o u
VD
0 o
1
CO
£ co co
m
CD
$H
CD
m
u
a
CD U
4X 2 5
3(2,4,5)
5
3
4
3(3,5,4)
4 3
5
3(3,4,5)
55 2 4
4
3(2,5,4)
Figure 2: The constructed coloring of B6 with 5 colors.
f : V(B3fc+3) ^{1, 2,..., j} by
f (B3(v))
9(f'(v),i,j) if v is even, 9(f'(v),j,i) if v is odd,
for every vertex v £ V(B3k). See Figure 2 for an illustration. Obviously, it is a proper coloring.
Now we show that the constructed coloring f satisfies the statement. Let P be a path in B3k+3 with endvertices in subtrees B3 (u) and B3(v), respectively. We distinguish three cases.
Case 1: u = v. Then P is inside B3(u) and we are done since the statement holds for k = 1.
Case 2: uv £ E(B3k+3). Without lost of generality, we assume that u is odd and u is a child of v, see Figure 1(b). Clearly, the path P contains the vertices u and v. Moreover, if none of the colors a = f '(u), b = f'(v) is inner and single on P, then both endvertices of P are in {u, v, x, y} where x, y are the vertices as on Figure 1(b). Observe that then in all possible cases, i or j is an inner single color on P or P = (u, v).
Case 3: u = v and uv £ E(B3k+3). Let P = (Pi,P2,P3) where Pi, P2, and P3 are subpaths of P in B3(u), B3k, and B3(v) respectively. As the length of P2 is at least 2, it contains an inner single color d by induction. Since d is inner, it does not appear neither on Pi nor P2. Therefore, the color d is also inner and single on P.	□
ti
VD
m
CD
$H
CD
m
u
a
CD U
From Theorem 2 we obtain the following upper bound. Corollary 3. \ ,,{!'>,,) <	for every n > 0.
Proof. It is enough to show that xP(Bn+1) < xP(Bn) +1 for every n > 0. To this end, if we color both copies of Bn in Bn+1 by (the same) parity vertex coloring with xP(Bn) colors, and we give the root of Bn+1 a new color, we obtain a parity vertex coloring of Bn+1 with Xv(Bn) + 1 colors.	□
On the other hand, Borowiecki et al. [1] showed that Xp(Pn) = [log2(n +1)] for every n-vertex path Pn. This gives us a trivial lower bound xP(Bn) > |~log2(2n + 1)] as Bn contains a 2n-vertex path. We ask if the following linear upper bound holds.
Question 4. Is it true that \r{ !>,,) > ^ for every n >0?
References
[1]	P. Borowiecki, K. Budajova, S. Jendrol', S. Krajci, Parity vertex colouring of graphs, Discuss. Math. Graph Theory 31 (2011) 183-195.
[2]	D. P. Bunde, K. Milans, D. B. West, H. Wu, Parity and strong parity edge-colorings of graphs, Combinatorica 28 (2008) 625-632.
i
[3]	A. A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: theory and applica-
tions, Acta Appl. Math. 66 (2001) 211-249.