Name
Abstract | ||
|---|---|---|
We prove that for every graph H, there exists ε>0 such that every n-vertex graph with no vertex-minors isomorphic to H has a pair of disjoint sets A, B of vertices such that |A|,|B|≥εn and A is complete or anticomplete to B. We deduce this from recent work of Chudnovsky, Scott, Seymour, and Spirkl (2018). This proves the analog of the Erdős–Hajnal conjecture for vertex-minors. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.disc.2018.09.007 | Discrete Mathematics |
Keywords | Field | DocType |
Vertex-minor,Erdős–Hajnal conjecture | Graph,Discrete mathematics,Combinatorics,Disjoint sets,Existential quantification,Vertex (geometry),Vertex (graph theory),Isomorphism,Erdős–Hajnal conjecture,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
341 | 12 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Chudnovsky | 1 | 390 | 46.13 |
| Sang-il Oum | 2 | 668 | 37.80 |