Artykuł w czasopiśmie
Brak miniatury
Licencja
Dostęp zamkniętyExcluding Hooks and their Complements
| dc.abstract.en | The long-standing Erdős-Hajnal conjecture states that for every n-vertex undirected graph H there exists ϵ(H)>0 such that every graph G that does not contain H as an induced subgraph contains a clique or an independent set of size at least nϵ(H). A natural weakening of the conjecture states that the polynomial-size clique/independent set phenomenon occurs if one excludes both H and its complement Hc. These conjectures have been shown to hold for only a handful of graphs: it is not even known if they hold for all graphs on 5 vertices. In a recent breakthrough, the symmetrized version of the Erdős-Hajnal conjecture was shown to hold for all paths. The goal of this paper is to show that the symmetrized conjecture holds for all trees on 6 (or fewer) vertices. In fact this is a consequence of showing that the symmetrized conjecture holds for any path with a pendant edge at its third vertex; thus we also give a new infinite family of graphs for which the symmetrized conjecture holds. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.contributor.author | Liebenau, Anita |
| dc.contributor.author | Choromanski, Krzysztof |
| dc.contributor.author | Falik, Dvir |
| dc.contributor.author | Pilipczuk, Marcin |
| dc.contributor.author | Patel, Viresh |
| dc.date.accessioned | 2024-01-25T00:06:38Z |
| dc.date.available | 2024-01-25T00:06:38Z |
| dc.date.issued | 2018 |
| dc.description.finance | Nie dotyczy |
| dc.description.number | 3 |
| dc.description.volume | 25 |
| dc.identifier.doi | 10.37236/6397 |
| dc.identifier.issn | 1097-1440 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/106698 |
| dc.identifier.weblink | https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p27 |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.ispartof | Electronic Journal of Combinatorics |
| dc.relation.pages | P3.27:1 - P3.27: 33 |
| dc.rights | ClosedAccess |
| dc.sciencecloud | nosend |
| dc.title | Excluding Hooks and their Complements |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |