A. Hajnal, Zs. Nagy, L. Soukup:

On the number of certain subgraphs of graphs without large cliques and independent subsets

A graph G=<V,E> without cliques or independent subsets of size |V| is called non-trivial. We say that G= <V,E> is almost-smooth iff it is isomorphic to G[V-W] whenever W is a subset of V with |W| < |V|. Given a graph G= <V,E> denote by I(G) the set of all isomorphism classes of induced subgraphs of cardinality |V|. It is shown that

Downloading the paper

  • gzipped tex file (21709 bytes)
  • gzipped dvi file (49419 bytes)
    appeared in "A Tribute to Paul Erdos ", e.d. A Baker, B. Bollobás, A. Hajnal, Cambridge University Press, 1990, p. 223-248.