ÀÏÍõÂÛ̳

Speaker:, professor emeritus of mathematics, University of Illinois at Urbana-Champaign

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\). 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. Complete bipartite graphs: For the complete bipartite graph \(K_{r,s}\)​, we prove the conjectured value of \(spec(K_{r,s}​)\) (it is the value \(r∘s\) given by the Hopf–Stiefel function).
2. Hypercube embeddings: We show that \(spec(G)\) for a connected \(n\)-vertex graph \(G\) equals the general lower bound \(⌈log2​n⌉\) if and only if \(G\) embeds in the hypercube \(Q_{⌈log2​n⌉​}\).
3. Distance powers of paths: We asymptotically compute \(spec(G)\) when \(G\) is the \(ℓ-th\) distance-power of a path, proving: spec\((P_n^ℓ​)∼ℓ⌈log2​n⌉\).
4. Bipartite graphs and separation from \(p(G)\): We disprove the conjecture that \(spec(G)=p(G)\) when \(G\) is bipartite by constructing bipartite graphs \(G\) such that \(p(G)/spec(G)\)​ is arbitrarily large; in particular, with \(spec(G)≥(1/3) ​k\) \(lnk\) and \(p(G)≤ 2k + k^{1/3}\).

These results are joint work with Peter Bradshaw and Sergey Norin.

Discrete Applied Math Seminar