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.

  • $\begingroup$ When you say "every pair of vertices" do you mean any neighbour pair of vertices or just any pair? $\endgroup$ – Arthur Nov 27 '15 at 0:15
  • 1
    $\begingroup$ Per @Arthur 's comment, it would otherwise seem the "graph" on $n$ vertices plays no role in the problem formulation. $\endgroup$ – hardmath Nov 27 '15 at 0:29
  • $\begingroup$ @Arthur, any pair. I changed the formulation to make it a complete graph. $\endgroup$ – Kostub Deshmukh Nov 27 '15 at 2:20
  • $\begingroup$ But then there is no reason to have a graph in the first place. The edges don't do anything. $\endgroup$ – Arthur Nov 27 '15 at 6:19
  • $\begingroup$ @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. $\endgroup$ – Kostub Deshmukh Nov 27 '15 at 16:45

Those are (more or less) the Ramsey numbers.

  • $\begingroup$ How did you get that? $\endgroup$ – Kostub Deshmukh Nov 27 '15 at 16:45
  • $\begingroup$ I knew them already from studying Math at Eindhoven University. $\endgroup$ – Pieter21 Nov 27 '15 at 17:19
  • $\begingroup$ I know what Ramsey numbers are. Can you explain how is this question related to them? $\endgroup$ – Kostub Deshmukh Nov 27 '15 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.