Skip to main content
eScholarship
Open Access Publications from the University of California

Connectivity, graph minors, and subgraph multiplicity

  • Author(s): Eppstein, David
  • et al.
Abstract

It is well known that any planar graph contains at most O(n) complete subgraphs. We extend this to an exact characterization: G occurs O(n) times as a subgraph of any planar graph, if and only if G is three-connected. Even more generally, G occurs O(n) times as a subgraph of the K_b,c free graphs, b >/= c, if and only if G is c-connected; G occurs O(n) times as a subgraph of the K_a-free graphs if and only if G is (a - 1)-connected. Our results use a simple Ramsey-theoretic lemma that may be of independent interest.

Main Content
Current View