报告题目：Strong parity edge-colorings of graphs
报告人：Douglas B. West, Zhejiang Normal University and University of Illinois
报告时间：2025年3月9日（周日）15:30-16:30
报告地点：20-306
报告摘要：An edge-coloring of a graph G is a {\it 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. The minimum numbers of colors in parity and strong parity edge-colorings of G are denoted p(G) and \spec(G), respectively.
We characterize strong parity edge-colorings and use this characterization to prove lower bounds on \spec(G) and answer several questions posed by Bunde, Milans, West, and Wu almost 20 years ago. The applications are as follows:
(1) For the complete bipartite graph K_{r,s}, we prove the conjectured value of \spec(K_{r,s}) (it is the value r\circ s given by the Hopf--Stiefel function).
(2) We show that \spec(G) for a connected n-vertex graph G equals the general lower bound \lceil \lg n \rceil if and only if $G$ embeds in the hypercube Q_{\lceil \lg n \rceil }.
(3) We asymptotically compute \spec(G) when G is the \ellth distance-power of a path, proving \spec(P_n^\ell)\sim\ell\lceil \lg n\rceil.
(4) We disprove the conjecture that \spec(G)=p(G) when G is bipartite by constructing bipartite graphs $G$ such that \spec(G)/p(G) is arbitrarily large; in particular, with $\spec(G)\ge{1\over4}4k\ln k$ and p(G)\le2k+k^{1/3}.
These results are joint work with Peter Bradshaw and Sergey Norin.
邀请人：朱绪鼎