The Ramsey number $R(G,H)$ of two graphs $G$ and $H$ is the smallest value $n$ such that any 2-coloring of the edges of $K_n$ contains either a red copy of $G$ or a blue copy of $H$ .

The chromatic number $X(G)$ of a graph $G$ is the smallest number $k$ such that $G$ is k-colorable. This means that:

  • We use $k$ colors to color the nodes of $G$.
  • Adjacent nodes in $G$ have different colors.

$C(H)$ = the order (that is, number of nodes) of the largest connected component of a graph $H$.

This is a relation between $X(G)$ and $C(H)$ :

$$R(G,H)\ge(X(G)- 1)(C(H) -1) + 1$$

Find $R({P_3,P_3})$, $R({P_3,C_4})$, $R({C_4,C_4})$ . Also, I need to prove that $R({K_{1,3},K_{1,3}})=6$ and $R({2K_3,K_3})=8$ .

I haven't tried anything yet hence I don't know where to start, any help is appreciated.

  • 1
    $\begingroup$ Try coloring $K_n$ for small $n$? $\endgroup$ – Mario Carneiro Dec 18 '12 at 9:31
  • $\begingroup$ How will that help me to find $R(P_3,P_3)$ and others..? $\endgroup$ – Dream Box Dec 18 '12 at 9:37
  • $\begingroup$ @Dream Box : The definition concerns $2$-colorings of the edges of $K_n$, so I guess it's a good place to start. $\endgroup$ – Patrick Da Silva Dec 18 '12 at 9:40
  • $\begingroup$ I'll admit that remark was rather tongue-in-cheek, but depending on the numbers involved, you may be able to produce all 2-colorings of $K_n$ and keep going up in $n$ until every 2-coloring has a copy of $G$ or of $H$. The combinatorics involved may make this prohibitive, though, I'm not sure at what point. $\endgroup$ – Mario Carneiro Dec 18 '12 at 9:41
  • 1
    $\begingroup$ I guess that for the small graphs $G$ and $H$ it's easier. I have answered a suggestion for those. $\endgroup$ – Patrick Da Silva Dec 18 '12 at 9:49

I will give you the idea for $R(P_3, P_3)$. Clearly $n \ge 3$ because your graph $K_n$ must have a subgraph isomorphic to $P_3$ and there is no such subgraph in $K_3$.

What about $n = 4$? Try all the colorings of $K_4$. Is there one that doesn't fit the definition? (I have actually verified that $R(P_3,P_3) = 4$.)

For the other ones, use the identity on $R(G,H)$ to get the smallest $n$ on which you can start checking if $R(G,H) = n$.

Hope that helps.

  • $\begingroup$ When you say try all the colorings of $K_4$ what do you mean? I know that the number of colors that can be used in a $K$ graph is $n$ so what am I missing here? $\endgroup$ – Dream Box Dec 18 '12 at 9:58
  • $\begingroup$ To show that a Ramsey number $R(G, H) = n$, you need to show that every $2$-coloring of the edges of $K_n$ contains either a copy of $G$ with all its edges of color $1$ or a copy of $H$ with all its edges of color $2$. $\endgroup$ – Andrew Uzzell Dec 18 '12 at 10:29
  • $\begingroup$ Well how is $R(P_3,P_3)=4$ when there are at least 4 colors to color $K_4$? $P_3$ is colored in 2 colors, yet there isn't any subgraph in $K_4$ that is colored with the same color twice? $\endgroup$ – Dream Box Dec 18 '12 at 10:53
  • $\begingroup$ The coloring is an edge-coloring, not a vertex-coloring. Also, it need not be (and almost never is) a proper coloring. $\endgroup$ – Andrew Uzzell Dec 18 '12 at 11:54
  • $\begingroup$ @Dream Box : You only need to find one $n$, because $K_{n+1}$ has $K_n$ as a subgraph, so if $K_n$ satisfies the property, so does $K_{n+1}$. I don't want to do the drawing here, it would take a while... so please do an edge-2-coloring of $K_4$ and see what happens. If you really need it I could try plotting one here. $\endgroup$ – Patrick Da Silva Dec 18 '12 at 18:04

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.