Search

A graph U is universal for a graph class C ∋ U , if every G ∈ C 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 ∞ as a minor. We prove the existence of uncountably many minor-closed classes of countable graphs that do not have a universal element. Some of our results and questions may be of interest from the finite graph perspective. 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. [ABSTRACT FROM AUTHOR]

Huynh et al. recently showed that a countable graph G which contains every countable planar graph as a subgraph must contain arbitrarily large finite complete graphs as topological minors, and an infinite complete graph as a minor. We strengthen this result by showing that the same conclusion holds if G contains every countable planar graph as a topological minor. In particular, there is no countable planar graph containing every countable planar graph as a topological minor, answering a question by Diestel and Kühn. Moreover, we construct a locally finite planar graph which contains every locally finite planar graph as a topological minor. This shows that in the above result it is not enough to require that G contains every locally finite planar graph as a topological minor. [ABSTRACT FROM AUTHOR]

The class of bipartite permutation graphs enjoys many nice and important properties. In particular, this class is critically important in the study of clique‐ and rank‐width of graphs, because it is one of the minimal hereditary classes of graphs of unbounded clique‐ and rank‐width. It also contains a number of important subclasses, which are critical with respect to other parameters, such as graph lettericity or shrub‐depth, and with respect to other notions, such as well‐quasi‐ordering or complexity of algorithmic problems. In the present paper we identify critical subclasses of bipartite permutation graphs of various types. [ABSTRACT FROM AUTHOR]

We investigate the question how 'small' a graph can be, if it contains all members of a given class of locally finite graphs as subgraphs or induced subgraphs. More precisely, we give necessary and sufficient conditions for the existence of a connected, locally finite graph H containing all elements of a graph class G. These conditions imply that such a graph H exists for the class G d consisting of all graphs with maximum degree < d which raises the question whether in this case H can be chosen to have bounded maximum degree. We show that this is not the case, thereby answering a question recently posed by Huynh et al. [ABSTRACT FROM AUTHOR]

For a graph G, the density of G, denoted D(G), is the maximum ratio of the number of edges to the number of vertices ranging over all subgraphs of G. For a class F of graphs, the value D (F) is the supremum of densities of graphs in F . A k-edge-colored graph is a finite, simple graph with edges labeled by numbers 1 , ... , k . A function from the vertex set of one k-edge-colored graph to another is a homomorphism if the endpoints of any edge are mapped to two different vertices connected by an edge of the same color. Given a class F of graphs, a k-edge-colored graph H (not necessarily with the underlying graph in F ) is k-universal for F when any k-edge-colored graph with the underlying graph in F admits a homomorphism to H . Such graphs are known to exist exactly for classes F of graphs with acyclic chromatic number bounded by a constant. The minimum number of vertices in a k-uniform graph for a class F is known to be Ω (k D (F)) and O (k D (F)) . In this paper we close the gap by improving the upper bound to O (k D (F)) for any rational D (F) . [ABSTRACT FROM AUTHOR]