On graph classes with minor-universal elements

arXiv2212.05498MaRDI QIDQ6420186FDOQ6420186

Authors: Agelos Georgakopoulos 

Publication date: 11 December 2022

Abstract: A graph $U$ is universal for a graph class $mathcalCiU$, if every $GinmathcalC$ is a minor of $U$. We prove the existence or absence of universal graphs in several natural graph classes, including graphs component-wise embeddable into a surface, and graphs forbidding $K_5$, or $K_{3,3}$, or $K_{i}nfty$ as a minor. We prove the existence of uncountably many minor-closed classes of countable graphs that (do and) do not have a universal element. Some of our results and questions may be of interest to the finite graph theorist. In particular, one of our side-results is that every $K_5$-minor-free graph is a minor of a $K_5$-minor-free graph of maximum degree 22.

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph theory (05C99)

This page was built for publication: On graph classes with minor-universal elements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6420186)