Speaker: Douglas B. West (Zhejiang Normal University and University of Illinois)
Title: Strong parity edge-colorings of graphs
Abstract: An edge-coloring of a graph G is a "parity edge-coloring" if for each path P in G, some color appears on an odd number of edges in P. It is a "strong parity edge-coloring" if for every open walk W in G, some color appears an odd number of times along W. We characterize strong parity edge-colorings and use this to answer several questions of Bunde, Milans, West, and Wu, who introduced these terms.
The applications concern p(G) and spec(G), which are the minimum numbers of colors in parity and strong parity edge-colorings of G, respectively.
(1) It is known that p(G) ≥ ceiling(lg n) for every connected n-vertex graph G; we show that spec(G)= ⌈lg n⌉ if and only if G is a subgraph of the hypercube Q_{⌈lg n⌉} .
(2) We prove the conjectured value of spec(K_{r,s}) .
(3) We derive lower bounds on spec(G) and use these to construct bipartite graphs G such that spec(G)/p(G) is arbitrarily large, disproving the conjecture that spec(G)=p(G) when G is bipartite.
The results are joint work with Peter Bradshaw and Sergey Norin.