Return to Question

Notice that every planar graph $G$ is a minor of a planar graph $H$ with maximum degree $\Delta(H)\leq 3$ (replace each vertex of $G$ by a sub-cubic tree to obtain $H$). The same idea can be applied to any $G$ embeddable into a fixed surface $\Sigma$. I'm wondering about possible generalisations of this fact to other minor-closed classes.

More concretely, let $\mathcal{C}$ be a minor-closed class of (finite) graphs. Let $m(\mathcal{C})$ be the least cardinal such that every $G\in \mathcal{C}$ is a minor of some $H\in \mathcal{C}$ with $\Delta(H)\leq m(\mathcal{C})$.

We saw above that for $C:={\text{graphs embeddable in $\Sigma$}}$, $m(\mathcal{C})=3$. But $m(\mathcal{C})$ is not always finite; consider for example the class of stars $\mathcal{C}=Forb(P_3)$, or $\mathcal{C}= \{\text{Apex graphs}\}$. One can obtain examples of classes $C$ with $m(\mathcal{C})$ equal to any desired number $k$: let $X$ be a (possibly infinite) $k$-regular graph, and let $\mathcal{C}$ be the class of finite minors of $X$. But these examples are superficial.

Question 1: Find other `natural' classes $\mathcal{C}$ with finite $m(\mathcal{C})$.

I would prefer classes that are not contained in the class of planar graphs.

Question 2: Find sufficient/necessary conditions on a class $\mathcal{C}$ to have finite $m(\mathcal{C})$.

ADDED 13/2/2022

Question 3: Is every proper minor-closed class of finite graphs contained in such a class $\mathcal{C}$ with finite $m(\mathcal{C})$?

Proper here means that $\mathcal{C}$ does not contain all finite graphs.

I can prove that $m(K_{3,3}-\text{minor-free})\leq 9$ and $m(K_{5}-\text{minor-free})\leq 22$, see the preprint On graph classes with minor-universal elements.

Notice that every planar graph $G$ is a minor of a planar graph $H$ with maximum degree $\Delta(H)\leq 3$ (replace each vertex of $G$ by a sub-cubic tree to obtain $H$). The same idea can be applied to any $G$ embeddable into a fixed surface $\Sigma$. I'm wondering about possible generalisations of this fact to other minor-closed classes.

More concretely, let $\mathcal{C}$ be a minor-closed class of (finite) graphs. Let $m(\mathcal{C})$ be the least cardinal such that every $G\in \mathcal{C}$ is a minor of some $H\in \mathcal{C}$ with $\Delta(H)\leq m(\mathcal{C})$.

We saw above that for $C:={\text{graphs embeddable in $\Sigma$}}$, $m(\mathcal{C})=3$. But $m(\mathcal{C})$ is not always finite; consider for example the class of stars $\mathcal{C}=\operatorname{Forb}(P_3)$, or $\mathcal{C}= \{\text{Apex graphs}\}$. One can obtain examples of classes $C$ with $m(\mathcal{C})$ equal to any desired number $k$: let $X$ be a (possibly infinite) $k$-regular graph, and let $\mathcal{C}$ be the class of finite minors of $X$. But these examples are superficial.

Question 1: Find other `natural' classes $\mathcal{C}$ with finite $m(\mathcal{C})$.

I would prefer classes that are not contained in the class of planar graphs.

Question 2: Find sufficient/necessary conditions on a class $\mathcal{C}$ to have finite $m(\mathcal{C})$.

ADDED 13/2/2022

Question 3: Is every proper minor-closed class of finite graphs contained in such a class $\mathcal{C}$ with finite $m(\mathcal{C})$?

Proper here means that $\mathcal{C}$ does not contain all finite graphs.

I can prove that $m(K_{3,3}-\text{minor-free})\leq 9$ and $m(K_{5}-\text{minor-free})\leq 22$, see the preprint On graph classes with minor-universal elements.

Notice that every planar graph $G$ is a minor of a planar graph $H$ with maximum degree $\Delta(H)\leq 3$ (replace each vertex of $G$ by a sub-cubic tree to obtain $H$). The same idea can be applied to any $G$ embeddable into a fixed surface $\Sigma$. I'm wondering about possible generalisations of this fact to other minor-closed classes.

More concretely, let $\mathcal{C}$ be a minor-closed class of (finite) graphs. Let $m_C$ be the least cardinal such that every $G\in \mathcal{C}$ is a minor of some $H\in \mathcal{C}$ with $\Delta(H)\leq m_C$.

We saw above that for $C:={\text{graphs embeddable in $\Sigma$}}$, $m_C=3$. But $m_C$ is not always finite; consider for example $\mathcal{C}=Forb(P_3)$, or $\mathcal{C}= \{\text{Apex graphs}\}$. One can obtain examples of classes $C$ with $m_C$ equal to any desired number $k$: let $X$ be a (possibly infinite) $k$-regular graph, and let $\mathcal{C}$ be the class of finite minors of $X$. But these examples are superficial.

Question 1: Find other `natural' classes $\mathcal{C}$ with finite $m_C$?

I would prefer classes that are not contained in the class of planar graphs.

Question 2: Find sufficient/necessary conditions on a class $\mathcal{C}$ to have finite $m_C$.

Notice that every planar graph $G$ is a minor of a planar graph $H$ with maximum degree $\Delta(H)\leq 3$ (replace each vertex of $G$ by a sub-cubic tree to obtain $H$). The same idea can be applied to any $G$ embeddable into a fixed surface $\Sigma$. I'm wondering about possible generalisations of this fact to other minor-closed classes.

More concretely, let $\mathcal{C}$ be a minor-closed class of (finite) graphs. Let $m(\mathcal{C})$ be the least cardinal such that every $G\in \mathcal{C}$ is a minor of some $H\in \mathcal{C}$ with $\Delta(H)\leq m(\mathcal{C})$.

We saw above that for $C:={\text{graphs embeddable in $\Sigma$}}$, $m(\mathcal{C})=3$. But $m(\mathcal{C})$ is not always finite; consider for example the class of stars $\mathcal{C}=Forb(P_3)$, or $\mathcal{C}= \{\text{Apex graphs}\}$. One can obtain examples of classes $C$ with $m(\mathcal{C})$ equal to any desired number $k$: let $X$ be a (possibly infinite) $k$-regular graph, and let $\mathcal{C}$ be the class of finite minors of $X$. But these examples are superficial.

Question 1: Find other `natural' classes $\mathcal{C}$ with finite $m(\mathcal{C})$.

I would prefer classes that are not contained in the class of planar graphs.

Question 2: Find sufficient/necessary conditions on a class $\mathcal{C}$ to have finite $m(\mathcal{C})$.

ADDED 13/2/2022

Question 3: Is every proper minor-closed class of finite graphs contained in such a class $\mathcal{C}$ with finite $m(\mathcal{C})$?

Proper here means that $\mathcal{C}$ does not contain all finite graphs.

I can prove that $m(K_{3,3}-\text{minor-free})\leq 9$ and $m(K_{5}-\text{minor-free})\leq 22$, see the preprint On graph classes with minor-universal elements.

Notice that every planar graph $G$ is a minor of a planar graph $H$ with maximum degree $\Delta(H)\leq 3$ (replace each vertex of $G$ by a sub-cubic tree to obtain $H$). The same idea can be applied to any $G$ embeddable into a fixed surface $\Sigma$. I'm wondering about possible generalisations of this fact to other minor-closed classes.

More concretely, let $\mathcal{C}$ be a minor-closed class of (finite) graphs. Let $m_C$ be the least cardinal such that every $G\in \mathcal{C}$ is a minor of some $H\in \mathcal{C}$ with $\Delta(H)\leq m_C$.

We saw above that for $C:={\text{graphs embeddable in $\Sigma$}}$, $m_C=3$. But $m_C$ is not always finite; consider for example $\mathcal{C}=Forb(P_3)$, or $\mathcal{C}= \{\text{Apex graphs}\}$. One can obtain examples of classes $C$ with $m_C$ equal to any desired number $k$: let $X$ be a (possibly infinite) $k$-regular graph, and let $\mathcal{C}$ be the class of finite minors of $X$. But these examples are superficial.

Question 1: Find other `natural' classes $\mathcal{C}$ with finite $m_C$?

I would prefer classes that are not contained in the class of planar graphs.

Question 2: Find sufficient/necessary conditions on the excluded minors of a class $\mathcal{C}$ to have finite $m_C$.

Notice that every planar graph $G$ is a minor of a planar graph $H$ with maximum degree $\Delta(H)\leq 3$ (replace each vertex of $G$ by a sub-cubic tree to obtain $H$). The same idea can be applied to any $G$ embeddable into a fixed surface $\Sigma$. I'm wondering about possible generalisations of this fact to other minor-closed classes.

More concretely, let $\mathcal{C}$ be a minor-closed class of (finite) graphs. Let $m_C$ be the least cardinal such that every $G\in \mathcal{C}$ is a minor of some $H\in \mathcal{C}$ with $\Delta(H)\leq m_C$.

We saw above that for $C:={\text{graphs embeddable in $\Sigma$}}$, $m_C=3$. But $m_C$ is not always finite; consider for example $\mathcal{C}=Forb(P_3)$, or $\mathcal{C}= \{\text{Apex graphs}\}$. One can obtain examples of classes $C$ with $m_C$ equal to any desired number $k$: let $X$ be a (possibly infinite) $k$-regular graph, and let $\mathcal{C}$ be the class of finite minors of $X$. But these examples are superficial.

Question 1: Find other `natural' classes $\mathcal{C}$ with finite $m_C$?

I would prefer classes that are not contained in the class of planar graphs.

Question 2: Find sufficient/necessary conditions on a class $\mathcal{C}$ to have finite $m_C$.