In:
Journal of Graph Theory, Wiley, Vol. 89, No. 3 ( 2018-11), p. 266-287
Abstract:
The Erdős–Hajnal conjecture states that for every given undirected graph H there exists a constant 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 . The conjecture is still open. Its equivalent directed version states that for every given tournament H there exists a constant such that every H ‐free tournament T contains a transitive subtournament of order at least . In this article, we prove that for several pairs of tournaments, H 1 and H 2 , there exists a constant such that every ‐free tournament T contains a transitive subtournament of size at least . In particular, we prove that for several tournaments H , there exists a constant such that every ‐free tournament T , where stands for the complement of H , has a transitive subtournament of size at least . To the best of our knowledge these are first nontrivial results of this type.
Type of Medium:
Online Resource
ISSN:
0364-9024
,
1097-0118
DOI:
10.1002/jgt.2018.89.issue-3
Language:
English
Publisher:
Wiley
Publication Date:
2018
detail.hit.zdb_id:
752540-0
detail.hit.zdb_id:
1468065-8
SSG:
17,1
Bookmarklink