Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656787 | Journal of Combinatorial Theory, Series B | 2015 | 4 Pages |
Abstract
We prove that for every k , there exists ck>0ck>0 such that every graph G on n vertices with no induced path PkPk or its complement Pk¯ contains a clique or a stable set of size ncknck.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
N. Bousquet, A. Lagoutte, S. Thomassé,