Premium
Excluding pairs of tournaments
Author(s) -
Choromanski Krzysztof
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22250
Subject(s) - combinatorics , tournament , mathematics , conjecture , transitive relation , graph , clique , induced subgraph , complement (music) , order (exchange) , undirected graph , discrete mathematics , chemistry , biochemistry , finance , complementation , vertex (graph theory) , economics , gene , phenotype
The Erdős–Hajnal conjecture states that for every given undirected graph 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. Its equivalent directed version states that for every given tournament H there exists a constant c ( H ) > 0 such that every H ‐free tournament T contains a transitive subtournament of order at least| V ( T ) | c ( H ) . In this article, we prove that for several pairs of tournaments, H 1 and H 2 , there exists a constant c ( H 1 , H 2 ) > 0 such that every { H 1 , H 2 } ‐free tournament T contains a transitive subtournament of size at least| V ( T ) | c ( H 1 , H 2 ) . In particular, we prove that for several tournaments H , there exists a constant c ( H ) > 0 such that every { H , H c } ‐free tournament T , where H c stands for the complement of H , has a transitive subtournament of size at least| V ( T ) | c ( H ) . To the best of our knowledge these are first nontrivial results of this type.