Let $C(s)$ be the smallest $n$ such that every connected graph on $n$ vertices has, as an induced subgraph either a complete graph $K_{s}$, a star $K(1,s)$ or a path $P_{s}$ of length $s$. Show that $C(s)\leq R(s)^{s}$, where $R(s)$, is the s Ramsey number.
Asked
Active
Viewed 170 times
4
-
this sounds like an incredibly nice result, however, I think it's pretty hard... do you have any ideas about it? – TJIF Feb 23 '13 at 03:58