Monochromatic partitionings of edge-colored graphs (Spring 2025)


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 partition if their vertex sets do not intersect and the union of their vertex sets is V(G). In this project, we will consider partitions in which each subgraph is monochromatic. We often focus on partitions of complete graphs, which are graphs with all possible edges present.


Erdős, Gyárfás, and Pyber proved that if we 3-color the edges of a complete graph, we can partition the graph into 2 monochromatic subgraphs. Haxell and Kohayakawa proved that if we r-color the edges of a complete graph (with sufficiently many vertices), then we can partition the graph into r monochromatic subgraphs. They were able to add the restriction that we can choose the r subgraphs to be trees of radius 2. In this project, we will consider monochromatic partitionings of edge-colored graphs, and we will explore what restrictions we can place on the subgraphs in our partitions.

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

(Project did not run)

People:

Pre-requisites: