Name
Abstract | ||
|---|---|---|
Ramsey's theorem says that for every clique H-1 and for every graph H-2 with no edges, all graphs containing neither of H-1, H-2 as induced subgraphs have bounded order. What if, instead, we exclude a graph H-1 with a vertex whose deletion gives a clique, and the complement H-2 of another such graph? This no longer implies bounded order, but it implies tightly restricted structure that we describe. There are also several related subproblems (what if we exclude a star and the complement of a star? what if we exclude a star and a clique? and so on) and we answer a selection of these. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1137/130946113 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
induced subgraphs,Ramsey's theorem | Discrete mathematics,Graph,Combinatorics,Clique,Vertex (geometry),Clique graph,Ramsey's theorem,A* search algorithm,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
29 | 1 | 0895-4801 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Chudnovsky | 1 | 390 | 46.13 |
| Sergey Norin | 2 | 47 | 10.86 |
| Bruce A. Reed | 3 | 1311 | 122.69 |
| Paul D. Seymour | 4 | 2786 | 314.49 |