Monochromatic covers of edge-colored graphs (Spring 2026)

A graph G consists of a set of vertices V(G) and a set of edges E(G) in which each edge connects two vertices. In an edge-coloring, colors are assigned to the edges of G. A subgraph of G is monochromatic if all the edges of that subgraph are the same color. We say a collection of subgraphs of G is a cover if the union of their vertex sets is V(G). In this project, we will consider covers in which each subgraph is monochromatic. We may also consider further restrictions on the covers, such as partitions, which are covers in which the vertex sets of the subgraphs are disjoint.

A famous open conjecture in graph theory is Ryser's conjecture, which can be stated in the special case of complete graphs as follows: for any r-coloring of the edges of the complete graph Kn, there is a monochromatic cover using at most r-1 subgraphs. We will learn about Ryser's conjecture and consider variations on the open problem. We will consider monochromatic covers of edge-colored graphs, and we will explore what restrictions we can place on the subgraphs in our covers.

For more information contact Grace McCourt (gmccourt@iastate.edu)

People:

• Grace McCourt (Postdoc)

• Shira Zerbib (Faculty)

Pre-requisites:

• Experience writing proofs preferred.

• Experience with graph theory or combinatorics preferred.

• Coding experience is not required, but may be useful.