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.

  • 1
    I guess that for the small graphs $G$ and $H$ it's easier. I have answered a suggestion for those.2012-12-18

1 Answers 1

0

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.

  • 0
    I can find some time to plot the graph by Sunday.2012-12-19