From Random Graphs to Graph Theory

Authors:

• Andrzej Ruciński

Abstract

Four graph theoretic problems, all born in the theory of random graphs, are presented. They have been stimulated by investigations of the existence and distribution of subgraphs of given type contained in the binomial random graph. The deterministic problems involve only the notions of a subgraph, subgraph count, and subgraph density and deal with balanced extensions of graphs, convex hulls, globally sparsest Ramsey graphs (in vertex-coloring case) and so called p-proportional graphs. © 1993, Elsevier Science & Technology.