Title | ||
---|---|---|
Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement |
Abstract | ||
---|---|---|
Erdős and Hajnal [Discrete Math 25 (1989), 37–52] conjectured that, for any graph H, every graph on n vertices that does not have H as an induced subgraph contains a clique or a stable set of size nɛ(H) for some ɛ(H)0. The Conjecture 1. known to be true for graphs H with |V(H)|≤4. One of the two remaining open cases on five vertices is the case where H is a four-edge path, the other case being a cycle of length five. In this article we prove that every graph on n vertices that does not contain a four-edge path or the complement of a five-edge path as an induced subgraph contains either a clique or a stable set of size at least n1/6. © 2011 Wiley Periodicals, Inc. J Graph Theory (This research was performed while the author was at Columbia University. © 2012 Wiley Periodicals, Inc.) |
Year | DOI | Venue |
---|---|---|
2012 | 10.1002/jgt.20626 | Journal of Graph Theory |
Keywords | Field | DocType |
induced subgraph,four-edge path,five-edge path,n vertex,graphs h,wiley periodicals,large clique,inc. j graph theory,graph h,size n,stable set | Discrete mathematics,Block graph,Combinatorics,Induced path,Induced subgraph,Independent set,Erdős–Hajnal conjecture,Clique (graph theory),Mathematics,Complement graph,Path graph | Journal |
Volume | Issue | ISSN |
70 | 4 | 0364-9024 |
Citations | PageRank | References |
7 | 0.73 | 3 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Maria Chudnovsky | 1 | 390 | 46.13 |
Yori Zwols | 2 | 45 | 6.34 |