# Find maximal clique in an multigraph with $n$ vertices, where each vertex is colored with $k$ colors.

You are given a multigraph with $n$ vertices. Every vertex is colored with maximum of $k$ colors. If two vertices share a color, there is an edge between them which is colored with that color. (A pair of vertices may have more than one edge as they may share more than one color.) There is at least one edge between every pair of vertices.

Define $F(n, k)$ to be the maximal number $s$ such that for any graph with $n$ vertices colored with $k$ colors as above, there is a clique of size $s$ where each edge is colored with the same color, i.e. there is guaranteed to be a set of $s$ vertices which share the same color.

So a few simple examples: $F(n, 1) = n$, clearly because every vertex has to have the same color.

It is easy to show that, $F(n, 2) = n-1$ and $F(n, n-1) = 2$.

With some effort one can prove that $F(9, 3)= 5$ and that can be generalized to $F(3n, 3) \ge n+2$.

My question is what is the method to solve this for general $n$ and $k$? Is there a way to reformulate this problem in a different way so that it resembles a known graph theory problem / theorem.

• When you say "every pair of vertices" do you mean any neighbour pair of vertices or just any pair? – Arthur Nov 27 '15 at 0:15
• Per @Arthur 's comment, it would otherwise seem the "graph" on $n$ vertices plays no role in the problem formulation. – hardmath Nov 27 '15 at 0:29
• @Arthur, any pair. I changed the formulation to make it a complete graph. – Kostub Deshmukh Nov 27 '15 at 2:20
• But then there is no reason to have a graph in the first place. The edges don't do anything. – Arthur Nov 27 '15 at 6:19
• @Arthur, I updated the problem formulation so that it is a multigraph with the edges colored. That's how I solved the simple cases. It is pigeon-hole principle problem, not a graph theory problem, and I am trying to formulate it as a graph theory problem so that it can be solved in the more general case. – Kostub Deshmukh Nov 27 '15 at 16:45