Unavoidable vertex-minors in large prime graphs

Cited 6 time in webofscience Cited 0 time in scopus
  • Hit : 403
  • Download : 0
A graph is prime (with respect to the split decomposition) if its vertex set does not admit a partition (A, B) (called a split) with vertical bar A vertical bar, vertical bar B vertical bar >= 2 such that the set of edges joining A and B induces a complete bipartite graph. We prove that for each n, there exists N such that every prime graph on at least N vertices contains a vertex-minor isomorphic to either a cycle of length n or a graph consisting of two disjoint cliques of size n joined by a matching.
Publisher
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
Issue Date
2014-10
Language
English
Article Type
Article
Keywords

RECOGNIZING CIRCLE GRAPHS; 4-CONNECTED GRAPHS; ISOTROPIC SYSTEMS; OBSTRUCTIONS; WIDTH

Citation

EUROPEAN JOURNAL OF COMBINATORICS, v.41, pp.100 - 127

ISSN
0195-6698
DOI
10.1016/j.ejc.2014.03.013
URI
http://hdl.handle.net/10203/189964
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 6 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0