UVic Discrete Math Seminar: Mengru Lin

An (m,n)-mixed graph consists of colored edges and colored arcs. MacGillivray and Trey extended Moon’s idea of a k-universal target graph to (m,n)-mixed graphs. In particular, they constructed an (m,n)-mixed graph H such that every (m,n)-mixed graph with at most k vertices is a subgraph of H.

In this talk, we focus on the special case of m-edge-colored graphs, where there are no colored arcs. We further consider a setting where the edge colors can be permuted. The permutations form a group Γ, which we call an m-switching group. We present results for the case when Γ is abelian and discuss how abelianization can be applied when Γ is non-abelian. We also introduce the concept of switching dimension and use these results to investigate how switching can reduce the order of universal targets for m-edge-colored graphs.