2
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Try coloring $K_n$ for small $n$? $\endgroup$
    – Mario Carneiro
    Commented Dec 18, 2012 at 9:31
  • $\begingroup$ How will that help me to find $R(P_3,P_3)$ and others..? $\endgroup$
    – Dream Box
    Commented Dec 18, 2012 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
    Commented Dec 18, 2012 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
    Commented Dec 18, 2012 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
    Commented Dec 18, 2012 at 9:49

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$
7
  • $\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
    Commented Dec 18, 2012 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
    Commented Dec 18, 2012 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
    Commented Dec 18, 2012 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
    Commented Dec 18, 2012 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
    Commented Dec 18, 2012 at 18:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .