Polynomail Expansion

Zdenek Dvorak

A class C of graphs has polynomial expansion if there exists a polynomial p such that for every graph G from C and for every integer r, each minor of G obtained by contracting disjoint subgraphs of radius at most r is p(r)-degenerate. Classes with polynomial expansion exhibit interesting structural, combinatorial, and algorithmic properties. In the talk, I will survey these properties and propose further research directions.

  • Combinatorial Theory Seminar