Vertex-minors and the Erdos-Hajnal conjecture

Cited 2 time in webofscience Cited 0 time in scopus
  • Hit : 98
  • Download : 0
We prove that for every graph H, there exists epsilon > 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 vertical bar A vertical bar, vertical bar B vertical bar >= epsilon 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 Erclas-Hajnal conjecture for vertex-minors. (C) 2018 Elsevier B.V. All rights reserved.
Publisher
ELSEVIER SCIENCE BV
Issue Date
2018-12
Language
English
Article Type
Article
Citation

DISCRETE MATHEMATICS, v.341, no.12, pp.3498 - 3499

ISSN
0012-365X
DOI
10.1016/j.disc.2018.09.007
URI
http://hdl.handle.net/10203/246681
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 2 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0