# Questions tagged [graph-minors]

A graph $H$ is called a minor of a graph $G$ if $H$ can be obtained from $G$ by contracting edges, deleting edges, and deleting isolated vertices.

74 questions
Filter by
Sorted by
Tagged with
1 vote
56 views

### Can $\delta(G)$ get arbitrarily large in relation to $\eta(G)$?

For any finite, simple, undirected graph $G$, let $\eta(G)$ be the maximum $n$ such that the complete graph $K_n$ is a minor of $G$, and let $\delta(G)$ be the minimum degree of $G$. In certain graphs ...
1 vote
54 views

### Hadwiger number and minimal degree (II)

This is a follow-up on an older question. Suppose $G$ is a finite simple graph and $\eta(G)$ is the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$. Let $\delta(G)$ is the minimal degree of ...
190 views

### Does every $4$-connected nonplanar graph contain a $K_5$-minor?

By Kuratowski's theorem, every nonplanar graph contains a (topological) minor of $K_5$ or $K_{3,3}$. But I observed that every time I construct a $4$-connected nonplanar graph, it always contains not ...
393 views

### Menger's theorem with restrictions on where the paths can begin and end

Let $k\in\mathbb N$. Given a finite graph with two subsets of vertices $X$ and $Y$, Menger's Theorem gives a criterion for when there are $k$ pairwise disjoint paths starting in $X$ and ending in $Y$. ...
1 vote
47 views

### Mac Lane-like condition for intrinsically linked graphs?

If any embedding of your graph in 3-space has two cycles that are linked, then your graph is intrinsically linked (such as the Petersen graph). These graphs generalise non-planar graphs since for ...
61 views

Let $G=(V,E)$ be a finite, simple, undirected graph. The Hadwiger number $\eta(G)$ of $G$ is defined to be the largest positive integer $n\in\mathbb{N}$ such that the complete graph $K_n$ is a minor ...
1 vote
85 views

### Connected partition number of a graph

Let $G=(V,E)$ be a finite, simple, undirected graph. We say that a partition ${\cal P}$ of $V$ into non-empty subsets of $V$ is connected if any two distinct blocks are connected by an edge, or more ...
176 views

### Induced minors and induced topological minors

Question: For which graphs $H$ is the following true? Every graph that contains $H$ as an induced minor also contains $H$ as an induced topological minor. Definitions: Let $G$ and $H$ be graphs. $H$ ...
37 views

### Expectation of Hadwiger number of a random graph

For any integer $n$, let ${\cal G}_n$ denote the set of simple, undirected graphs $G = (V, E)$ where $V = \{1,\ldots,n\}$. The Hadwiger number $\eta(G)$ of a finite graph $G$ is the maximum integer $m$...
1 vote
71 views

### Expected value of the difference of the Hadwiger number and the chromatic number

If $G$ is a finite, simple, undirected graph, its Hadwiger number $\eta(G)$ is the maximum integer $n$ such that $K_n$ is a minor of $G$. Given any integer $k>0$ let $E_k$ be the expected value of ...
394 views

### Does the purported proof of Rota's conjecture provide an algorithm for calculating the forbidden minors of matroids over arbitrary finite fields?

About six years ago there was a proof announced and later outlined in a notice from AMS. However right now I can only seem to find forbidden minor characterizations for matroids linearly ...
240 views

### Forbidden minors of a graph with treewidth at most 4

I am interested in the graphs with treewidth 5 because of its relationship with realization dimension of a graph (See here). In this PhD thesis, 75 lists of minimal forbidden minors of a graph with ...
148 views

### Edge contraction-like graph operation

Previously asked on MSE. Given a simple graph $G=(V,E)$ and an edge $uv\in E$, the contraction of $uv$ refers to the replacement of the vertices $u$ and $v$ with a new vertex $w$ such that the edges ...
136 views

### Are K_t-minor free graphs on small vertex sets understood?

In a paper on Hadwiger's conjecture, https://web.math.princeton.edu/~pds/papers/hadwiger/paper.pdf, Seymour explains various results on excluding the complete graph as a minor. In particular, there is ...
36 views

### Forbidden structures for generalized hypertree width

Generalized hypertree width is a tree-width-like parameter for hypergraphs, which plays an important role in the study of constraint satisfaction problems and related areas. For its more well-known ...
262 views

### Directed graph minor theorems

In proving the graph minor theorem, Robertson and Seymour proved a stronger statement, namely that the directed graph minor theorem is true, using the definition A directed graph is a minor of ...
1 vote
27 views

Let $G=(V,E)$ be a connected, simple, finite, undirected graph. The Hadwiger number $\eta(G)$ is the maximum integer $n\in \mathbb{N}$ such that $K_n$ is a minor of $G$. We say that $G$ is ...
1 vote
200 views

### Effect of removing an edge on Hadwiger number

If $G=(V,E)$ is a finite, simple, undirected graph, then by $\eta(G)$ we denote the maximum integer $n\in \mathbb{N}$ such that $K_n$ is a minor of $G$. If $e\in E$ we write $G\setminus e$ to denote ...
321 views

### Does minimal degree $n$ imply a $K_n$ minor

Is it true that any finite graph has a $K_n$ minor, where $n$ is a minimal vertex degree?
1 vote
19 views

### Hadwiger number in vertex collapse in a bipartite graph

If $G=(V,E)$ is a finite graph, let the Hadwiger number $\eta(G)$ equal the largest integer $n$ such that the complete graph $K_n$ is a minor of $G$. Is there a bipartite graph $G$ on more than $3$ ...
155 views

### Generalized graph-minor theorem?

Consider the following generalized graph-minor theorem: GM($κ,λ$): Given any collection $S$ of $κ$ simple undirected graphs each with less than $λ$ vertices, there are distinct graphs $G,H$ in $S$ ...
82 views

### Forbidden minor characterization of polytope skeletons

Say that a graph is "$d$-dimensional" if it is the node-disjoint union of $1$-skeletons of closed convex polytopes in $d$ dimensions, or a subgraph thereof. So the $2$-dimensional graphs are exactly ...
282 views

### Disjoint paths between four vertices

Consider the following property of an undirected graph: For any four distinct vertices $a,b,c,d$, there is a path from $a$ to $b$ and a path from $c$ to $d$ such that the two paths do not share any ...
369 views

### What is a hypergraph minor?

Is there a theory of hypergraph minors? I could only find some attempts to define them at papers/theses, whose main topic was something else. What would be a useful definition? Does the hypergraph ...
92 views

### Increasing Hadwiger number by collapsing vertices of distance $2$

If $G=(V,E)$ is a finite, simple, undirected graph, the Hadwiger number $\eta(G)$ is defined to be the size of the largest complete minor of $G$. Is there a finite graph $G=(V,E)$ with the following ...
161 views

Let $G=(V,E)$ be a simple, undirected graph. Suppose that ${\cal S}$ is a collection of non-empty, connected, and pairwise disjoint subsets of $V$. Let $G({\cal S})$ be the graph with vertex set ${\... 2 votes 0 answers 48 views ### Flat or linkless embeddings of graph with fixed projection The problem of finding whether a given planar diagram of a graph, with over- and under-crossings, is a linkless embedding or not has unknown complexity (Kawarabayashi et al., 2010). My first question ... 2 votes 1 answer 146 views ### Induced minors of$\{0,1\}^\omega$Let$G=(V,E)$be a simple, undirected graph. Suppose that${\cal S}$is a collection of non-empty, connected, and pairwise disjoint subsets of$V$. Let$G({\cal S})$be the graph with vertex set${\...
90 views

Is there an infinite, simple, undirected graph $G=(V,E)$ such that there is $n\in\mathbb{N}$ with the following properties? $K_n$ is a minor of $G$, but $K_{n+1}$ is not a minor of $G$, and if $F$ ...
304 views

### Two disjoint trees

Let $G$ be a graph and let $A_1, A_2 \subseteq V(G)$ be disjoint sets of vertices. Let us call $(A_1, A_2)$ independent if there exist vertex-disjoint trees $T_1, T_2 \subseteq G$ within $G$ which ...
123 views

1 vote
113 views

### Ordinal corresponding to well-quasi-order on graphs

Let $K$ be an infinite cardinal. Then, by the Robertson–Seymour theorem, the set of graphs with fewer than $K$ vertices and edges form a well-quasi-order. In terms of $K$, what is the maximal order ...
305 views

### Bounds on degrees of minors obtained by edge contractions of regular graphs

Given a connected $d$-regular graph $G=(V,E)$, generate a sequence of minors by performing only edge contractions and loop deletions (as, e.g., in Karger's algorithm) until the graph collapses to a ...