David Wood: Universal Graph Product Structures

Description of video

Date: 12/4/20
Speaker :Wood David

Abstract. This talk will survey recent results that describe graphs as subgraphs of products of simpler graphs. The starting point is the following theorem: every planar graph is a subgraph of the strong product of some treewidth 7 graph and a path. This result has been the key to solving several open problems, for example, regarding the queue-number and nonrepetitive chromatic number of planar graphs. The result generalises to provide a universal graph for planar graphs. In particular, if T7 is the universal treewidth 7 graph (which is explicitly defined), then every countable planar graph is a subgraph of the strong product of T7 and the infinite 1-way path. This result generalises in various ways for many sparse graph classes: graphs embeddable on a fixed surface, graphs excluding a fixed minor, map graphs, etc. For example, we prove that for every fixed graph X, there is an explicitly defined countable graph G that contains every countable X-minor-free graph as a subgraph, and G has several desirable properties such as every n-vertex subgraph of G has a O(n)-separator. On the other hand, as a lower bound we strengthen a theorem of Pach (1981) by showing that if a countable graph G contains every countable planar graph, then G must contain an infinite complete graph as a minor.