# 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.

83
questions

4
votes

0
answers

82
views

### Reference to a definition of a graph homology

Let $G$ be a graph, and define $C_k$ to be the free abelian group on the following homomorphisms from graphs $H$ such that $K_k$ is a minor of $H$ without needing to do any vertex deletions, only edge ...

0
votes

0
answers

77
views

### Is there is a constant $c$ such that toroidal graphs are minor-$c$-colorable?

A toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross.
A minor of graph G is a graph obtained from G by ...

0
votes

1
answer

99
views

### Hadwiger number of the Hadwiger-Nelson graph on $\mathbb{R}^2$

If $G =(V,E)$ is a simple, undirected graph (finite or infinite), and $\kappa \neq \emptyset$ is a cardinal, we say that the complete graph $K_\kappa$ is a minor of $G$ if there is a collection ${\...

3
votes

1
answer

124
views

### Bounding the size of clique minor of the union of two graphs

Suppose that graphs $A$ and $B$ with $V(A)=V(B)$ have Hadwiger numbers $a$ and $b$. That is, $K_a$ and $K_b$ are the largest clique minors of $A$ and $B$, respectively.
Are there upper bounds on the ...

1
vote

1
answer

120
views

### Complete minor graphs

Is there any result or known way to find complete minors of graphs? I want to find complete minors of generalized Petersen graphs and $3$-regular graphs. I guess that generalized Petersen graphs $G (n,...

0
votes

0
answers

24
views

### What is known about "overlapping" models/minors of graphs

Suppose we are given a graph $G$ from a graph class of sublinear treewidth and connected subgraphs $G_1,G_2,..,G_l$ of $G$ such that each $G_i$ intersects (shares a node with) constant many other $G_j$...

0
votes

0
answers

59
views

### Hadwiger numbers of (-1)-isomorphic graphs

We say that simple, undirected graphs $G, H$ are (-1)-isomorphic if there is a bijection $\varphi:V(G)\to V(H)$ such that for all $v\in V$ we have that the induced subgraphs $G\setminus\{v\}$ and $H\...

4
votes

0
answers

95
views

### Classes of graphs that are minors of bounded degree graphs in the same class

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 ...

1
vote

0
answers

61
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

0
answers

56
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 ...

6
votes

1
answer

416
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 ...

5
votes

1
answer

420
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

0
answers

52
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 ...

4
votes

0
answers

65
views

### Increasing the Hadwiger number by making any pair of non-adjacent points adjacent

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

0
answers

103
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 ...

3
votes

0
answers

333
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$ ...

2
votes

0
answers

47
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

0
answers

74
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 ...

6
votes

1
answer

540
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 ...

4
votes

2
answers

359
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 ...

4
votes

0
answers

247
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 ...

4
votes

1
answer

170
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 ...

3
votes

0
answers

47
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 ...

6
votes

1
answer

465
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

0
answers

32
views

### Contraction criticality and edge-adding criticality for Hadwiger number

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

1
answer

201
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 ...

10
votes

2
answers

388
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

0
answers

24
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$ ...

6
votes

0
answers

171
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$ ...

4
votes

0
answers

91
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 ...

6
votes

1
answer

291
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 ...

6
votes

2
answers

483
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 ...

0
votes

1
answer

103
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 ...

0
votes

1
answer

170
views

### Is every finite graph an induced minor of $\omega^2$?

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

53
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

153
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 ${\...

2
votes

1
answer

93
views

### Compactness of Hadwiger number

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$ ...

11
votes

3
answers

391
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 ...

3
votes

0
answers

132
views

### Hadwiger number of Erdös-Faber-Lovasz graphs

For any set $X$, let $[X]^2 = \big\{\{a,b\}:a,b \in X, a\neq b\big\}$.
We call a finite, simple, undirected graph $G=(V,E)$ an $n$-Erdös-Faber-Lovasz (EFL-) graph if there are $n$ subsets $S_1,\...

0
votes

1
answer

131
views

### Large complete minors of $\mathbb{Z}^\omega$

Let $x,y\in \mathbb{Z}^\omega$ and let $x,y\in\mathbb{Z}^\omega$ form an edge if there is $i\in\omega$ such that $|x_i - y_i|=1$ and $ x_k = y_k$ for all $k\in \omega\setminus\{i\}$.
$K_\omega$, the ...

0
votes

1
answer

110
views

### Complete minors of the grid graphs $\mathbb{Z}^n$

Let $n>1$ be an integer. We say that two points $(x_1,\ldots,x_n),(y_1,\ldots,y_n)\in\mathbb{Z}^n$ are a member of the edge set $E_n$ if and only if $$\sum_{i=1}^n|x_i-y_i| = 1.$$
Question. Given ...

1
vote

1
answer

234
views

### Is this totally unimodular family?

Is it possible to prove this matrix family only contains totally unimodular matrices?
The matrix has dimensions $\frac{3n(n-1)}2$ rows and $n+\frac{n(n-1)}2$ columns.
To every pair $(i,i')$ with $1\...

1
vote

0
answers

118
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 ...

6
votes

1
answer

326
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 ...

5
votes

0
answers

93
views

### Increasing the Hadwiger number by identifying non-adjacent points

This is a specialization of a more general, still unanswered question.
Suppose $G$ is a finite, simple graph. Let $h(G)$ denote the Hadwiger number, that is, the maximum $n\in\mathbb{N}$ such that $...

2
votes

1
answer

85
views

### Hadwiger critical graphs of arbitrarily high chromatic number

This is an update to an older question admitting a trivial example to answer it.
Suppose $G$ is a finite simple graph. Let $h(G)$ denote the Hadwiger number of $G$; that is, the maximum $n\in\mathbb{...

-2
votes

1
answer

130
views

### Identifying two non-adjacent vertices and the effect on the Hadwiger number [closed]

Suppose $G$ is a finite simple graph. Let $h(G)$ denote the Hadwiger number of $G$; that is, the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$.
What is an example of a graph $G_0=(V_0, ...

4
votes

0
answers

218
views

### Two types of criticality

Suppose $G$ is a finite simple graph. Let $h(G)$ denote the Hadwiger number (synonym: connected pseudoachromatic number, cf. [Abrams-Berman 2014, p. 315]) of $G$; that is, the maximum $n\in\mathbb{N}$ ...

6
votes

1
answer

103
views

### Characterizing SP-DAGs by Forbidden Minors?

So it's well-known that an alternative way to define a series-parallel (undirected graph) is by the forbidden minor $K_4$. Is there a known analog of this definition for directed graphs — ...

0
votes

1
answer

45
views

### Complete minors in a "redoubled" graph

For any finite, simple, undirected graph $G=(V,E)$ denote by $G_2 = (V_2, E_2)$ the graph, in which $V_2$ and $E_2$ are defined as follows:
$V_2 = \big(V\times\{1\}\big) \cup \big(V\times \{2\}\big)$...