Small Induced-Universal Graphs for Planar Graphs

Definitions and mathematical statement

For each integer $n\geq 1$, let $\mathcal P_n$ denote the class of planar graphs with exactly $n$ vertices. Here graphs are interpreted as finite, undirected, and simple; the supplied statement does not explicitly specify these conventions, so they require confirmation. A graph is planar if it admits a drawing in the plane in which edges meet only at common endpoints. For a graph $U$ and $S\subseteq V(U)$, the induced subgraph $U[S]$ has vertex set $S$ and precisely those edges of $U$ whose endpoints both belong to $S$. Say that $U$ is induced-universal for $\mathcal P_n$ if \[ \forall G\in\mathcal P_n\;\exists\text{ an injection }\varphi:V(G)\longrightarrow V(U)\;\forall x,y\in V(G),\ x\ne y:\quad \{x,y\}\in E(G)\iff \{\varphi(x),\varphi(y)\}\in E(U). \] Define \[ u_{\mathrm{pl}}(n)=\min\left\{|V(U)|:U\text{ is a finite simple graph induced-universal for }\mathcal P_n\right\}. \] The host graph $U$ is not required to be planar. The minimum is well-defined, since a disjoint union of representatives of the finitely many isomorphism classes in $\mathcal P_n$ is an admissible host.

Problem. Determine $u_{\mathrm{pl}}(n)$ as a function of $n$. The question asks for the minimum order; the supplied literature assessment emphasizes the unresolved asymptotically exact minimum, without specifying a conjectured formula or asymptotic equivalent. The source does not address $n=0$.

Source qualifications. The supplied record labels the problem open. Its dated literature assessment reports induced-universal constructions with $n^{1+o(1)}$ vertices and states that the asymptotically exact minimum remains open; these are supplied curation claims, not independently verified here. The original excerpt also includes an $O(n^{3/2})$ bound attributed to Babai, Chung, Erdős, Graham, and Spencer, with reference label [2]. Because that sentence precedes the numbered question and its surrounding context and bibliography are absent, its applicability to this induced-universality problem is unresolved.

Short English statement

For each positive integer $n$, determine the fewest vertices in a graph that contains every $n$-vertex planar graph as an induced subgraph. The host may be nonplanar. The finite simple graph convention and the source's historical bound need confirmation; the supplied open status and dated literature assessment require independent review.

Sources

• Local UnsolvedMath registry: data/unsolvedmath/problems.json, with catalog/problems.json as the additional-record registry; supplied permanent ID $30004965$, title "Small Induced-Universal Graphs for Planar Graphs," exact source code catalogue entry. The supplied record marks the statement corrected_verified and says it was checked against the official report; this is a recorded verification claim, not a verification performed here.
• Supplied report citation: Graph Theory (2023), Oberwolfach Reports, pp. 5--78, DOI 10.4171/owr/2022/1. https://doi.org/10.4171/owr/2022/1. The literature-source label is "Oberwolfach Report 1/2022," and the record gives proposed year 2022. The inconsistent year labels require bibliographic confirmation.
• The excerpt places the question with "Further applications of the product structure theorem," Gwenaël Joret, joint work with Vida Dujmović, Louis Esperet, Cyril Gavoille, Piotr Micek, and Pat Morin. The record supplies no individual proposer; this talk attribution does not establish individual authorship of the problem.
• Esperet, Joret, and Morin, Sparse universal graphs for planarity. https://arxiv.org/abs/2010.05779. This is a supplied literature reference; the claimed induced-universality bound has not been checked here.
• Historical attribution retained from the excerpt: Babai, Chung, Erdős, Graham, and Spencer, reference [2], for an $O(n^{3/2})$ bound. No full citation for [2] is supplied, and the excerpt does not establish which preceding question that bound concerns.
• Literature assessment checked at 2026-08-22: the supplied curation labels the problem open, reports $n^{1+o(1)}$-vertex induced-universal constructions for $n$-vertex planar graphs, and says the asymptotically exact minimum remains open. This exact date records supplied dated curation, not independently verified literature review. The background explicitly requests independent verification of time-sensitive status and cited claims.