Name
Abstract | ||
|---|---|---|
The Erd¿s-Hajnal Conjecture states that for every given H there exists a constant c ( H ) 0 such that every graph G that does not contain H as an induced subgraph contains a clique or a stable set of size at least | V ( G ) | c ( H ) . The conjecture is still open. However some time ago its directed version was proved to be equivalent to the original one. In the directed version graphs are replaced by tournaments, and cliques and stable sets by transitive subtournaments. Both the directed and the undirected versions of the conjecture are known to be true for small graphs (or tournaments), and there are operations (the so-called substitution operations) allowing to build bigger graphs (or tournaments) for which the conjecture holds. In this paper we prove the conjecture for an infinite class of tournaments that is not obtained by such operations. We also show that the conjecture is satisfied by every tournament on at most 5 vertices. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.jctb.2014.11.003 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
erdos-hajnal conjecture,regularity lemma,tournaments | Discrete mathematics,Combinatorics,Clique,Induced subgraph,Lonely runner conjecture,Independent set,New digraph reconstruction conjecture,Erdős–Hajnal conjecture,Conjecture,Collatz conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
112 | C | 0095-8956 |
Citations | PageRank | References |
1 | 0.41 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eli Berger | 1 | 182 | 52.72 |
| Krzysztof Choromanski | 2 | 124 | 23.56 |
| Maria Chudnovsky | 3 | 310 | 61.32 |