Name
Abstract | ||
|---|---|---|
The ErdAs-Hajnal conjecture states that for every graph H, there exists a constant delta(H)> 0, such that if a graph G has no induced subgraph isomorphic to H, then G contains a clique or a stable set of size at least |V (G)| (delta(H)). This conjecture is still open. We consider a variant of the conjecture, where instead of excluding H as an induced subgraph, both H and H (c) are excluded. We prove this modified conjecture for the case when H is the five-edge path. Our second main result is an asymmetric version of this: we prove that for every graph G such that G contains no induced six-edge path, and G (c) contains no induced four-edge path, G contains a polynomial-size clique or stable set. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s00493-014-3000-z | Combinatorica |
Field | DocType | Volume |
Discrete mathematics,Reconstruction conjecture,Combinatorics,Clique,Induced path,Graph factorization,Induced subgraph,Induced subgraph isomorphism problem,Independent set,New digraph reconstruction conjecture,Mathematics | Journal | 35 |
Issue | ISSN | Citations |
4 | 0209-9683 | 3 |
PageRank | References | Authors |
0.50 | 5 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Chudnovsky | 1 | 390 | 46.13 |
| Paul D. Seymour | 2 | 2786 | 314.49 |