Optimal strong parity edge-coloring of complete graphs

Written with Kevin Milans, Douglas B. West, and Hehui Wu.
Combinatorica, 28(6): 625-632, 2008.

A preliminary version of this paper is included in arXiv:math.CO/0602341. That version also includes some material from a different paper.

Download

A preprint from this website: gzipped postscript or pdf
From arXiv: (preliminary version with other material) arXiv:math.CO/0602341

Abstract:

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 sp(G) be the least number of colors in an edge-coloring of G having no open parity walk (a strong parity edge-coloring). Always sp(G) >= p(G) >= Χ'(G). We prove that sp(K_n)=2^{⌈lg n⌉}-1 for all n. The optimal strong parity edge-coloring of K_n is unique when n is a power of 2, and the optimal colorings are completely described for all n.

Note: In the paper, the symbol used for the strong parity edge coloring number is "p hat" rather than sp; I don't know how to add "hats" in html.