Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 116
  • Download : 0
A homogeneous set of a graph G is a set X of vertices such that 2 <= vertical bar X vertical bar < vertical bar V(G)vertical bar and no vertex in V(G) - X has both a neighbor and a non-neighbor in X. A graph is prime if it has no homogeneous set. We present an algorithm to decide whether a class of graphs given by a finite set of forbidden induced subgraphs contains infinitely many non-isomorphic prime graphs. (C) 2018 Elsevier B.V. All rights reserved.
Publisher
ELSEVIER SCIENCE BV
Issue Date
2019-03
Language
English
Article Type
Article
Citation

DISCRETE APPLIED MATHEMATICS, v.257, pp.60 - 66

ISSN
0166-218X
DOI
10.1016/j.dam.2018.10.030
URI
http://hdl.handle.net/10203/253966
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0