Deepak Bal | Montclair State University

Abstract

Suppose the edges of a graph have been colored with red and blue by an adversary. Can you always find a large connected subgraph whose edges are all blue or all red (i.e. a large monochromatic component)? How about a long monochromatic path or cycle? Can you always find a collection of a few monochromatic components (or paths, or cycles) which covers all the vertices of the graph? What if the color palette has size r instead of just 2? In this talk we will discuss such questions, specifically when the underlying graph is a random graph.