To refer to this page use:

`http://arks.princeton.edu/ark:/88435/pr12094`

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 Gyarfas 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 Gyarfas [5] and for which we give a short proof. (C) 2013 Elsevier Inc. All rights reserved. |

Publication Date: | Mar-2014 |

Electronic Publication Date: | 7-Dec-2013 |

Citation: | Chudnovsky, Maria, Seymour, Paul. (2014). Extending the Gyarfas-Sumner conjecture. JOURNAL OF COMBINATORIAL THEORY SERIES B, 105 (11 - 16. doi:10.1016/j.jctb.2013.11.002 |

DOI: | doi:10.1016/j.jctb.2013.11.002 |

ISSN: | 0095-8956 |

EISSN: | 1096-0902 |

Pages: | 11 - 16 |

Type of Material: | Journal Article |

Journal/Proceeding Title: | JOURNAL OF COMBINATORIAL THEORY SERIES B |

Version: | Author's manuscript |

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.