2021/09/01 by Tony Huynh, Huynh, Tony, Bojan Mohar +7 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2109.00327
openalex publication_date 2021/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Stanislaw Ulam asked whether there exists a universal countable planar graph (that is, a countable planar graph that contains every countable planar graph as a subgraph). János Pach (1981) answered this question in the negative. We strengthen this result by showing that every countable graph that contains all countable planar graphs must contain (i) an infinite complete graph as a minor, and (ii) a subdivision of the complete graph Kt with multiplicity t, for every finite t. On the other hand, we construct a countable graph that contains all countable planar graphs and has several key properties such as linear colouring numbers, linear expansion, and every finite n-vertex subgraph has a balanced separator of size O(√(n)). The graph is T6\boxtimes P ∞, where Tk is the universal treewidth-k countable graph (which we define explicitly), P ∞ is the 1-way infinite path, and \boxtimes denotes the strong product. More generally, for every positive integer t we construct a countable graph that contains every countable Kt-minor-free graph and has the above key properties. Our final contribution is a construction of a countable graph that contains every countable Kt-minor-free graph as an induced subgraph, has linear colouring numbers and linear expansion, and contains no subdivision of the countably infinite complete graph (implying (ii) above is best possible).