Math.wvu.edu

Optimal Parity Edge-Coloring of Complete Graphs David P. Bunde∗, Kevin Milans†, Douglas B. West‡, Hehui Wu§ A parity walk in an edge-coloring of a graph is a walk along which each color is used an even number of times. Let p(G) be the least number of colors in an edge-coloring of G having no parity path (a parity edge-coloring). Let p(G) be the least number of colors in an edge-coloring of G having no open parity walk (a strong parity edge-coloring).
Always p(G) ≥ p(G) ≥ χ (G). We prove that p(Kn) = 2 lg n − 1 for all n. The optimalstrong parity edge-coloring of Kn is unique when n is a power of 2, and the optimalcolorings are completely described for all n.
Our work began by studying which graphs embed in the hypercube Qk, the graph with vertexset {0, 1}k in which vertices are adjacent when they differ in exactly one coordinate. Color- ing each edge with the position of the bit in which its endpoints differ yields two necessary conditions for the coloring inherited by a subgraph G: 1) every cycle uses each color an even number of times, 2) every path uses some color an odd number of times.
Existence of a k-edge-coloring satisfying conditions (1) and (2) is also sufficient for a con- nected graph G to be a subgraph of Qk. This characterization of subgraphs of Qk was provedas early as 1972, by Havel and Mov´ arek [6]. The problem was studied as early as 1953 by Define the usage of a color on a walk to be the parity of the number of times it appears as the walk is traversed. A parity walk is a walk in which the usage of every color is even.
Condition (1) for an edge-coloring states that every cycle is a parity walk, and (2) states ∗Computer Science Department, Knox College, Galesburg, IL, [email protected]. Partially supported †Department of Computer Science, University of Illinois, Urbana IL, [email protected]‡Department of Mathematics, University of Illinois, Urbana, IL, [email protected]. Work supported in part by the NSA under Award No. MDA904-03-1-0037.
§Department of Mathematics, University of Illinois, Urbana, IL.
In general, a parity edge-coloring is an edge-coloring with no parity path, and a strong parity edge-coloring (spec) is an edge-coloring with no open parity walk (that is, every parity walk is closed). Although some graphs do not embed in any hypercube, using distinct colors on the edges produces a spec for any graph. Hence the parity edge-chromatic number p(G) and the strong parity edge-chromatic number p(G), defined respectively to be the minimum numbers of colors in a parity edge-coloring of G and a spec of G, are well defined. Elementary results on these parameters appear in [4].
When T is a tree, p(T ) = p(T ) = k, where k is the least integer such that T embeds in Qk. Since incident edges of the same color would form a parity path of length 2, everyparity edge-coloring is a proper edge-coloring, and hence p(G) ≥ χ (G), where χ (G) denotes the edge-chromatic number. Although there are graphs G with p(G) > p(G) [4], it remains unknown how large p(G) can be when p(G) = k. It also remains unknown whether there is a bipartite graph G with p(G) > p(G).
When n is a power of 2, we will prove that the optimal spec of Kn is unique, which will help us determine p(Kn) for all n. With a suitable naming of the vertices, we call thisedge-coloring of Kn the “canonical” coloring.
F , let K(A) be the complete graph with vertex set A.
canonical coloring of K(A) is the edge-coloring f defined by f (uv) = u + v, where u + v denotes binary vector addition. When n = 2k, we treat the vertex as F , the canonical coloring of K(A) is a spec. Consequently, if n = 2k, then p(Kn) = p(Kn) = χ (Kn) = n − 1.
Proof. If W is an open walk, then its endpoints differ in some bit i. Thus in the canonical coloring the total usage of colors flipping bit i along W is odd, and hence some color has odd usage on W . The canonical coloring of K( k F ) uses 2k − 1 colors (the color 0k is not used).
Since every complete graph is a subgraph of the next larger complete graph, we obtain p(Kn) ≤ 2 lg n − 1. In Section 2, we use linear algebra to show that this upper bound isexact; this is our main result.
The canonical coloring is relevant to a less restrictive edge-coloring problem. A walk of length 2k is repetitive if, for each 1 ≤ i ≤ k, the ith and (k + i)th edges have the same color.
A Thue coloring is an edge-coloring having no repetitive path, and the Thue number t(G) is the minimum number of colors in a Thue coloring of G. Every parity edge-coloring is a Thue coloring, and Alon, Grytczuk, Haluszczak, and Riordan [2] showed that t(Kn) ≤ 2 lg n − 1using the canonical coloring. Obtaining non-trivial lower bounds on t(Kn) remains an openproblem. Our result implies that a Thue coloring of Kn better than the canonical coloringmust contain a parity walk.
To further motivate our focus on complete graphs, we note that our main result implies a special case of Yuzvinsky’s Theorem [10]. Yuzvinsky’s Theorem provides a tight lower bound on the number of distinct sums induced by two sets of binary vectors and makes use of the Hopf–Stiefel–Pfister function.
Definition 1.3 (Hopf–Stiefel–Pfister function) If r and s are positive integers, define r ◦ s to be the least integer n such that (x + y)n is in the ideal (xr, ys) of F2[x, y].
Hence, r ◦ s is the least n such that for each k with n − s < k < r, n is even. Recently, Plagne [8] found a simple formula for the Hopf–Stiefel–Pfister function, and K´ Theorem 1.4 ([8]; see also [7]) r ◦ s = mink∈ Theorem 1.5 (Yuzvinsky [10]; see also [1], [3], [5]) Given A, B ⊆ A, b ∈ B}. If |A| ≥ r and |B| ≥ s, then |C| ≥ r ◦ s.
Our main result implies the special case of Yuzvinsky’s Theorem where A = B. Indeed, if F and |A| = r, then the canonical (and optimal) coloring of K(A) uses 2 lg r − 1 colors, none of which is 0k. By construction, these colors all lie in C; therefore |C| ≥ 2 lg r = r ◦ r.
The canonical coloring extends to complete bipartite graphs in a natural way: if A, B ⊆ F and K(A, B) is the complete bipartite graph with partite sets A and B, then the edge- coloring defined by f (ab) = a + b is a spec. Because Yuzvinsky’s Theorem is tight, for each F with |A| = r, |B| = s, and |C| = r◦s. Consequently, p(K We conjecture that equality holds. A direct proof in the graph-theoretic setting would imply In this section, we use linear algebra to prove that p(Kn) ≥ 2 lg n − 1. The main idea isto introduce an additional vertex without needing additional colors until a power of 2 is reached. We begin by proving that every optimal spec of Kn is a canonical coloring when nis a power of 2.
Definition 2.1 An edge-coloring f of a graph G satisfies the 4-constraint if whenever f (uv) = f (xy) and vx ∈ E(G), also uy ∈ E(G) and f (uy) = f (vx).
Lemma 2.2 If f is a parity edge-coloring in which every color class is a perfect matching, Proof. Otherwise, given f (uv) = f (xy), the edge of color f (vx) incident to u forms a parity path of length 4 with uv, vx, and xy.
Theorem 2.3 If f is a parity edge-coloring of Kn in which every color class is a perfectmatching, then f is a canonical coloring and n is a power of 2.
Proof. Every edge is a canonically colored copy of K2. Let R be a largest vertex set suchthat |R| is a power of 2 and f restricts to a canonical coloring on R. Define j by |R| = 2j−1.
under which f is the canonical coloring.
Since f is canonical, every color used within R by f forms a matching of R. Let c be a color not used within R; since c is used on a perfect matching, c matches R to some set U .
F as follows: for x ∈ R, obtain φ (x) by appending 0 to φ(x); for x ∈ U obtain φ (x) by appending 1 to φ(x ), where x is the neighbor of x in color c. Within R , we henceforth refer to the vertices by their names under φ .
By Lemma 2.2, the 4-constraint holds for f . The 4-constraint copies the coloring from the edges within R to the edges within U . To see this, consider x , y ∈ U arising from x, y ∈ R, with f (xx ) = f (yy ) = c. Now f (x y ) = f (xy) = x + y = x + y , using the 4-constraint, the fact that f is canonical on R, and the definition of φ . Hence f is canonical Finally, let u be the name of the color on the edge 0ju, for u ∈ U . For any v ∈ R, let w = u + v; note that w ∈ U . Both 0jv and uw have color v, since f is canonical within R and within U . By applying the 4-constraint to {v0j, 0jw, wu}, we conclude that f (uv) = f (0jw) = w. Since w = u + v, this completes the proof that f is canonical on R .
In connection with this uniqueness result, Mubayi asked whether a stability property holds. That is, when n is a power of 2, does there exist a parity edge-coloring or a spec of Kn that has only (1 + o(1))n colors but is “far” from the canonical coloring? Now we begin the algebraic observations needed for the main result. Relative to any k-edge-coloring f , the parity vector π(W ) of a walk W is the binary k-tuple whose ith bit agrees in parity with the usage of color i along W . Let the parity space Lf be the set ofparity vectors of closed walks. We note that Lf is a vector space.
Lemma 2.4 If f is an edge-coloring of a connected graph G, then Lf is a binary vectorspace.
f ⊆ F , it suffices to show that L is closed under binary addition. Given a u, u-walk W and a v, v-walk W , let P be a u, v-path in G, and let P be its reverse. Following W, P, W , P in succession yields a u, u-walk with parity vector π(W ) + π(W ).
For a binary vector space L, let w(L) denote the least number of nonzero coordinates of any vector in L. For an edge-coloring f of Kn, w(Lf ) determines whether f is a spec.
Lemma 2.5 If an edge-coloring f of a graph G is a spec, then w(Lf ) ≥ 2. The converseholds when G = Kn.
Proof. If the parity vector of a closed walk W has weight 1, then one color has odd usage in W (say on edge e). Now W − e is an open parity walk, and f is not a spec.
If f is not a spec, then π(W ) = 0 for some open walk W . In Kn, the ends of W are adjacent, and adding that edge yields a closed walk whose parity vector has weight 1.
Lemma 2.6 For colors a and b in an optimal spec f of Kn, there is some closed walk Won which the colors having odd usage are a, b, and one other.
Proof. We use Lemma 2.5 repeatedly. Since f is optimal, merging the colors a and b into a single color a yields an edge-coloring f that is not a spec. Hence under f there is a closed walk W on which f has odd usage for only one color c. Also c = a , since otherwise f has odd usage on W for only a or b. With c = a and the fact that f has odd usage for at least two colors on W , both a and b also have odd usage on W , and W is the desired walk.
The same idea as in Lemma 2.6 shows that w(Lf ) ≥ 3 when f is an optimal spec of Kn, but we do not need this observation. We note, however, that the condition w(Lf ) ≥ 3 isthe condition for Lf to be the set of codewords for a 1-error-correcting code. Indeed, whenn = 2k and f is the canonical coloring, Lf is a perfect 1-error-correcting code of length n − 1.
A dominating vertex in a graph is a vertex adjacent to all others.
Lemma 2.7 If f is an edge-coloring of a graph G with a dominating vertex v, then Lf isthe span of the parity vectors of triangles containing v.
Proof. By definition, the span is contained in Lf . Conversely, consider any π(W ) ∈ Lf .
Let S be the set of edges with odd usage in W , and let H be the spanning subgraph of G with edge set S. Since the total usage at each vertex of W is even, H is an even subgraph of G. Hence H decomposes into cycles, which are closed walks, and π(W ) is the sum of the It therefore suffices to show that S is the set of edges that appear in an odd number of the triangles formed by v with edges of H − v. Each edge of H − v is in one such triangle, so we need consider only edges involving v. An edge vw lies in an odd number of these triangles if and only if dH−v(w) is odd, which occurs if and only if w ∈ NH(v), since dH(w) is even.
By definition, vw ∈ E(H) if and only if vw has odd usage in W and hence lies in S.
Lemma 2.8 If f is an optimal spec of Kn that uses some color less than n/2 times, then fextends to a spec of Kn+1 using the same colors.
Proof. View Kn+1 as arising from Kn by adding a vertex u. Let a be a color used less thann/2 times by f , and let v be a vertex of Kn at which a does not appear.
We use f to define f on E(Kn+1). Let f agree with f on E(Kn), and let f (uv) = a. To define f on each remaining edge uw, first let b = f (vw). By Lemma 2.6, there is a closed walk W with odd usage precisely for a and b and some third color c under f . Let f (uw) = c.
Note that f uses the same colors as f . It remains only to show that f is a spec. To do this we prove that w(Lf ) ≥ 2, by showing that Lf ⊆ Lf . By Lemma 2.7, it suffices to showthat π(T ) ∈ Lf when T is a triangle in Kn+1 containing v.
Triangles not containing u lie in the original graph and have parity vectors in Lf . Hence we consider the triangle T formed by {u, v, w}. Now π(T ) = π(W ) ∈ Lf , where W is thewalk used to specify f (uw).
Proof. If some color class in an optimal spec is not a perfect matching, then p(Kn) =p(Kn+1), by Lemma 2.8. This vertex absorption cannot stop before the number of verticesreaches a power of 2, because when every color class is a perfect matching the coloring is canonical, by Theorem 2.3. It cannot continue past 2 lg n vertices, since then the maximum degree equals the number of colors. Hence p(Kn) = p(K2 lg n ) = 2 lg n − 1.
Corollary 2.10 If f is an optimal spec of Kn, then f is obtained by deleting vertices fromthe canonical coloring of K2 lg n .
Proof. By Lemma 2.8, we may extend f to an optimal spec f of K2 lg n ; by Theorem 2.3,f is the canonical coloring.
It is natural to wonder whether every edge-coloring of Kn that satisfies the 4-constraint is a spec or a parity edge-coloring. One can construct examples that show the answer is no.
Similarly, not every parity edge-coloring of Kn is a spec. Nevertheless, it may be that everyoptimal parity edge-coloring is a spec. We offer the following conjecture, which in [4] we Conjecture 2.11 p(Kn) = p(Kn) for every positive integer n.
We thank Dan Cranston, Will Kinnersley, Brighten Godfrey, Michael Barrus, and Mohit [1] N. Alon, Combinatorial Nullstellensatz. Combin., Prob., and Computing 8 (1999), 7-29.
[2] N. Alon, J. Grytczuk, M. Haluszczak, and O. Riordan, Nonrepetitive colorings of graphs.
Random Structures Algorithms 21 (2002), 336–346.
as, and I. Leader, Sums in the grid. Discrete Math. 162 (1996), 31-48.
[4] D. P. Bunde, K. Milans, D. B. West, and H. Wu, Parity Edge-Coloring of Graphs. preprint.
[5] S. Eliahou and M. Kervaire, Sumsets in vector spaces over finite fields. J. Number Theory 71 arek, B-valuation of graphs. Czech. Math. J. 22, 338–351.
arolyi, A Note on the Hopf–Stiefel Function, Manuscript.
[8] A. Plagne, Additive number theory sheds extra light on the Hopf–Steifel ◦ function.
L’Enseignement Math. 49 (2003) 109-116.
[9] H. Shapiro, The embedding of graphs in cubes and the design of sequential relay circuits, Bell Telephone Laboratories Memorandum, July 1953.
[10] S. Yuzvinsky, Orthogonal pairings of Euclidean spaces. Michigan Math. J. 28 (1981), 109-119.

Source: http://www.math.wvu.edu/~milans/research/parity/parshort.pdf