Unavoidable induced subgraphs in large graphs with no homogeneous sets

Cited 5 time in webofscience Cited 0 time in scopus
  • Hit : 250
  • Download : 0
A homogeneous set of an n-vertex graph is a set X of vertices (2 <= vertical bar X vertical bar <= n - 1) such that every vertex not in X is either complete or anticomplete to X. A graph is called prime if it has no homogeneous set. A chain of length t is a sequence of t+1 vertices such that for every vertex in the sequence except the first one, its immediate predecessor is its unique neighbor or its unique non-neighbor among all of its predecessors. We prove that for all n, there exists N such that every prime graph with at least N vertices contains one of the following graphs or their complements as an induced subgraph: (1) the graph obtained from K-1,K-n by subdividing every edge once, (2) the line graph of K-2,K-n, (3) the line graph of the graph in (1), (4) the half-graph of height n, (5) a prime graph induced by a chain of length n, (6) two particular graphs obtained from the half-graph of height n by making one side a clique and adding one vertex.
Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
Issue Date
2016-05
Language
English
Article Type
Article
Citation

JOURNAL OF COMBINATORIAL THEORY SERIES B, v.118, pp.1 - 12

ISSN
0095-8956
DOI
10.1016/j.jctb.2016.01.008
URI
http://hdl.handle.net/10203/208636
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 5 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0