## Abstract

Sauer [Combinatorics, 1 (1993), pp. 361-377] has conjectured that for any tree T and any clique K, the class Forb(T, K) of graphs that induces neither T nor K is not vertex Ramsey. This conjecture is implied by an even stronger conjecture of Gyárfás and independently by Sumner, that Forb(T, K) is x-bounded. Until now, for all trees T, if Forb(T, K) was known to not be vertex Ramsey, then Forb(T, K) was also known to be x-bounded. In this paper we introduce a new class of trees, spiders with toes, which includes all trees T such that Forb(T) is known to be x-bounded as well as other trees for which it is not known to be x-bounded. We show that for every spider with toes T, Forb(T, K) is not vertex Ramsey.

Original language | English (US) |
---|---|

Pages (from-to) | 373-380 |

Number of pages | 8 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 10 |

Issue number | 3 |

DOIs | |

State | Published - Aug 1997 |

## Keywords

- Chromatic number
- Hypergraph
- Ramsey

## ASJC Scopus subject areas

- Mathematics(all)