UVic Discrete Math Seminar: Gary MacGillivray

In 1964, JW Moon constructed a k-universal graph, for every fixed integer k. This is a (large) graph that contains every graph on k vertices as an induced subgraph. In 1968, he used a similar method to construct, for every fixed integer k, a k-universal tournament. This is a tournament that contains every tournament on k vertices as a sub-tournament. We provide a slight generalization that enables it to be extended to (m, n)-mixed graphs, which are objects that have coloured edges and coloured arcs. For every fixed integer k we construct a k-universal (m, n)-mixed graph, that is an (m, n)-mixed graph that contains all (m, n)-mixed graphs on k vertices as an induced subgraph. Joint work with Trey Ross.