Ramsey's theorem states that any 2-color edge coloring of a sufficiently large graph contains a monochromatic complete subgraph. Does there exist something like Ramsey's theorem but for vertex colorings? Like, for any 2-color vertex coloring of a sufficiently large graph contains a monochromatic complete subgraph (but this time with the vertices colored and not the edges). Or is there someway to translate the vertex problem in an edge coloring problem such that we can use Ramsey's theorem?
Is there a Ramsey’s theorem equivalent for vertex colorings
coloringgraph theoryramsey-theory
Related Solutions
This proof considers the even-sized subsets of vertices of a pentagon. There are 16 such subsets: The empty set, the five sides of $P$, the five diagonals of $P$, and the five sets of size 4.
Each subset corresponds to a vertex in the graph we want to color. The color of the edge between two vertices is found by considering the symmetric difference of their two subsets.
The symmetric difference operation $\triangle$ takes any two such subsets to a third. If the subsets are different, the result cannot be empty, and so must be one of the other types: a side, a diagonal, or size 4. The coloring strategy is simply to use one color for each of these three types.
Any triangle $\{a,b,c\}$ in the graph we are coloring consists of three edges, colored according to the type of $f(a) \triangle f(b)$, the type of $f(b) \triangle f(c)$, and the type of $f(a) \triangle f(c)$.
This is easy to reason about, because the identity $$ \underbrace{(f(a) \triangle f(b))}_{\mbox{subset 1}} \; \triangle \; \underbrace{(f(b) \triangle f(c))}_{\mbox{subset 2}} = \underbrace{f(a) \triangle f(c)}_{\mbox{subset 3}} $$ tells us that if there is a monochromatic triangle, then there must be two subsets of the same type whose symmetric difference is also of the same type.
But the symmetric difference of two sides is either a diagonal or of size 4, depending on whether the sides shared a vertex or not.
Similarly, the symmetric difference of two diagonals is either a side or of size 4, depending on whether the diagonals shared a vertex or not.
And finally, the symmetric difference of two distinct subsets of size 4 (so each subset is only missing a single vertex) has to be a subset of size 2 (namely the two missing vertices), and is thus either a side or a diagonal.
$\scriptsize\mbox{(You might wonder whether the final coloring of the graph is symmetric in all three colors, since it is clearly symmetric}$ $\scriptsize\mbox{in the first two (by rearranging the pentagon to make the diagonals be the sides), and surprisingly, the answer is yes!)}$
The complete graph $K_{14}$ is much bigger than needed for this result; here are three proper subgraphs with the same property.
I. Every $2$-coloring of the complete bipartite graph $K_{3,7}$ contains a monochromatic $C_4$.
Let $K_{3,7}$ have partite sets $V_1,V_2$ with $|V_1|=3$ and $|V_2|=7$. Each vertex in $V_2$ is joined by edges of one color to two vertices in $V_1$. By the pigeonhole principle, two vertices in $V_2$ are joined by edges of the same color to the same two vertices in $V_1$.
II. Every $2$-coloring of the complete graph $K_6$ contains a monochromatic $C_4$. (This was shown in Misha Lavrov's answer; the following argument is perhaps slightly simpler.)
We may assume that there is a vertex $x$ which is incident with at most two blue edges. In fact, we may assume that $x$ is incident with exactly two blue edges; otherwise $x$ would be incident with four red edges, call them $xa_1$, $xa_2$, $xa_3$, $xa_4$, and then we could consider a vertex $y\notin\{x,a_1,a_2,a_3,a_4\}$ and proceed as in paw88789's answer. (It may be even easier to observe that the subgraph induced by $\{a_1,a_2,a_3,a_4\}$ contains either a red $P_3$ or a blue $C_4$.)
So let $x$ be incident with exactly two blue edges, $xy$ and $xz$. If one of the remaining three vertices is joined by blue to both $y$ and $z$, then we have a blue $C_4$. On the other hand, if each of those three vertices is joined by red to a vertex in $\{y,z\}$, then two of them are joined by red to the same vertex in $\{y,z\}$, and also to $x$, making a red $C_4$.
III. Every $2$-coloring of the complete bipartite graph $K_{5,5}$ contains a monochromatic $C_4$.
The proof is left as an exercise for the reader.
Best Answer
For vertex colouring the theorem is called "The Pigeon Hole Principle". It says that no matter how you colour the vertices of the complete graph with $(n-1)r+1$ vertices with $r$ colours you can always find a mono-chromatic copy of $K_n$.
Moreover, there exists a colouring of the complete graph with $(n-1)r$ vertices with $r$ colours with no monochromatic $K_n$.
Nobody cares about this because the answer is trivial.