A preliminary version of this paper is included in arXiv:math.CO/0602341. That version also includes the material that eventually became a different paper.
Download
Abstract:
A parity walk in an edge-coloring of a graph is a walk traversing each color an even number of times. We introduce two parameters. Let p(G) be the least number of colors in a parity edge-coloring of G (a coloring having no parity path). Let sp(G) be the least number of colors in a strong parity edge-coloring of G (a coloring having no open parity walk). Note that sp(G) >= p(G) >= Χ'(G).
The values p(G) and sp(G) may be equal or differ, with equality conjectured for all bipartite graphs. If G is connected, then p(G) >= ⌈lg |V(G)⌉, with equality for paths and even cycles (Cn needs one more color for odd n). The proof that sp(Kn)=2⌈lg n⌉-1 for all n will appear later; the conjecture that p(Kn)=sp(Kn) is proved here for n < = 16 and other cases. Also, p(K2,n)=sp(K2,n)=2⌈n/2⌉. In general, sp(Km,n) < = m'⌈n/m'⌉, where m'=2⌈lg m⌉. We compare these to other parameters and pose many open questions.
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.