### Abstract

Say a set H of graphs is heroic if there exists k such that every graph containing no member of H as an induced subgraph has cochromatic number at most k. (The cochromatic number of G is the minimum number of stable sets and cliques with union V(G) Assuming an old conjecture of Gyárfás and Sumner, we give a complete characterization of the finite heroic sets.This is a consequence of the following. Say a graph is k-split if its vertex set is the union of two sets A, B, where A has clique number at most k and B has stability number at most k. For every graph H_{1} that is a disjoint union of cliques, and every complete multipartite graph H_{2}, there exists k such that every graph containing neither of H_{1}, H_{2} as an induced subgraph is k-split.This in turn is a consequence of a bound on the maximum number of vertices in any graph that is minimal not k-split, a result first proved by Gyárfás [5] and for which we give a short proof.

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

Pages (from-to) | 11-16 |

Number of pages | 6 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 105 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 2014 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

### Keywords

- Induced
- Ramsey
- Subgraph