Forcing monochromatic induced subgraphs

Abstract

We prove that for all $c\in \mathbb{N}$ and nonnull graphs $H_1,\dots ,H_t$, there exists $n\in \mathbb{N}$ such that if $G$ is a $c$-edge-colored complete graph with no monochromatic induced copy of the complete join of $H_1,\dots ,H_t$, then $V(G)$ is the union of $n$ sets $V_1,\dots ,V_n$ such that within each set $V_j$ with $|V_j|\ne 1$, the edges of some color form a graph that excludes at least one of $H_1,\dots ,H_t$ as an induced subgraph. In fact, the same holds even if the colors overlap, and with a different list of graphs $H_1,\dots ,H_t$ assigned to each color. When $H_1,\dots ,H_t$ each have a single vertex, this is Ramsey's theorem, and when $c=2$, this is the "excluding pairs of graphs" theorem of Chudnovsky, Scott, and Seymour.

Topics & keywords