Strong parity edge-colorings of graphs

An edge-coloring of a graph G assigns a color to each edge of G . An edge-coloring is a parity edge-coloring if for each path P in G , it uses some color on an odd number of edges in P . It is a strong parity edge-coloring if for every open walk W in G , it uses some color an odd number of times along W . The minimum numbers of colors in parity and strong parity edge-colorings of G are denoted p ( G ) and p ˆ ( G ) , respectively. We characterize strong parity edge-colorings and use this to prove lower bounds on p ˆ ( G ) and answer several questions of Bunde, Milans, West, and Wu. The applications are as follows. (1) We prove the conjecture that p ˆ ( K s , t ) = s ∘ t , where s ∘ t is the Hopf–Stiefel function. (2) We show that p ˆ ( G ) for a connected n -vertex graph G equals the known lower bound ⌈ log 2 n ⌉ if and only if G is a subgraph of the hypercube Q ⌈ log 2 n ⌉ . (3) We asymptotically compute p ˆ ( G ) when G is the ℓ th distance-power of a path, proving p ˆ ( P n ℓ ) ∼ ℓ log 2 n . (4) We disprove the conjecture that p ˆ ( G ) = p ( G ) when G is bipartite by constructing bipartite graphs G such that p ˆ ( G ) / p ( G ) is arbitrarily large; in particular, with p ˆ ( G ) ≥ 1 − o ( 1 ) 3 k ln k and p ( G ) ≤ 2 k + k 1 / 3 .