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

56
questions

**1**

vote

**0**answers

23 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

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

**7**

votes

**2**answers

209 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

16 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

136 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

73 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

**2**answers

196 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

83 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

137 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

33 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

144 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

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

**9**

votes

**1**answer

142 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

113 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

123 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

93 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

170 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

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

**2**

votes

**1**answer

224 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

90 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

76 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

99 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

206 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

79 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

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

**-1**

votes

**1**answer

51 views

### Complete minors in graphs of bounded diameter

For positive integers $m, d\in \mathbb{N}$ consider the following statement:
$\mathsf{S}(m,d):$ There is $N\in\mathbb{N}$ such that the complete graph $K_m$ on $m$ vertices is a minor of any finite ...

**7**

votes

**1**answer

117 views

### Is the “surface-minor” ordering of plane graphs a well-quasi-ordering?

A plane graph is a finite simple graph with a fixed embedding into the two-sphere. The embedding induces an embedding on a minors of a plane graph (i.e. a graph obtained by successive removal of ...

**2**

votes

**1**answer

157 views

### Minors of graphs with infinite chromatic number

Let $G=(V,E)$ be an infinite simple, undirected graph with $\chi(G) \geq \aleph_0$. Is there a minor $M$ of $G$ such that
$M\not\cong G$, and
$\chi(M)=\chi(G)$
?

**2**

votes

**1**answer

102 views

### Complete minors and minimal degree

Is there for every positive integer $n\in\mathbb{N}$ a finite, simple, undirected graph $G=(V,E)$ with the following property?
$G$ does not have a complete minor with more than $\frac{\delta(G)}{n}$...

**1**

vote

**2**answers

144 views

### Does anyone know a specific polynomial-time algorithm to detect if a given signed graph contains an odd-K4 as a signed minor?

By signed graph, I mean each edge is designated either odd or even (e.g. as in Guenin's result for weakly bipartite graphs).

**2**

votes

**0**answers

56 views

### Is there an established notion of 'signed treewidth' for signed graphs?

By a signed graph, I mean a graph where each edge is designated as either odd or even (as in Guenin's result for weakly bipartite graphs).
It is well-known that for (unsigned, or usual) graphs, ...

**4**

votes

**0**answers

160 views

### Hadwiger's conjecture in the language of graph homomorphisms

Consider the following statement:
(S): If $G$ is not a complete graph, then there is a minor $M$ of $G$ such that
$M \not \cong G$, and
there is a graph homomorphism $f:G\to M$.
Hadwiger's ...

**2**

votes

**1**answer

141 views

### Size of forbidden minors for treewidth

For any $k$, the class of graphs of treewidth at most $k$ can be characterized by a finite set of forbidden minors.
For treewidth $1$ and $2$, the set is of size $1$. Then for treewidth $3$, the set ...

**6**

votes

**1**answer

94 views

### Graph minors, and Kronecker product

Let $X$ and $Y$ be graphs and consider the Kronecker product: $Z = X \otimes Y$. Is it true that if $X$ excludes an $M$-minor, $Z$ excludes an $M \otimes Y$ minor?
I am particularly interested in the ...

**2**

votes

**3**answers

203 views

### Hadwiger number and minimal degree

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$. If $\delta(G)$ is the minimal degree of $G$, do we have $\delta(G)\leq\eta(G)$?

**5**

votes

**1**answer

219 views

### Is there a polynomial-time algorithm to check if a signed graph contains an odd-K5 minor?

I suspect this exists, if anyone has a reference please that would be very helpful.
By signed graph, I mean each edge is designated either odd or even (e.g. as in Guenin's result for weakly bipartite ...

**1**

vote

**0**answers

78 views

### An algorithm to compute the number of graphs of size n with a given graph as a minor

I'm looking for any results regarding computing the number of graphs of size $n$ which have a given graph $H$ as a minor. Are there any known algorithms which are more efficient than a brute force ...

**3**

votes

**2**answers

200 views

### Asymptotics of list size in Robertson-Seymour theorem

A planar graph cannot have $K_5$ and $K_{3,3}$ as minors. Robertson-Seymour theorem generalizes this by stating for every genus $g$ there is a finite list of forbidden minor graphs that are ...

**3**

votes

**1**answer

305 views

### Is there a version of Robertson-Seymour's graph minor theorem known to apply to signed graphs?

Here a signed graph is one where each edge is signed either odd or even. A cycle is odd or even according to the sum of the signs of its edges. For a given signed graph, a resigning may be performed ...

**8**

votes

**0**answers

263 views

### A separation property of graphs of bounded tree-width

The following separation property of trees is well-known and in fact easy to prove (see e.g. the paper "Covering a hypergraph of subgraphs" by Noga Alon, Lemma 2.2)
Let $T$ be a tree and $r, m$ non-...

**3**

votes

**1**answer

102 views

### What is the relation between Hadwiger number and Treewidth?

Is there any general relation between Hadwiger number and Treewidth of a graph? Intuitively I think Hadwiger number is greater than or equal to Treewidth, but I couldn't prove it.

**1**

vote

**1**answer

94 views

### What is the relation between size of maximum clique and branchwidth?

Let $bw(G)$ be the branchwidth of graph $G$ and $\omega(G)$ be the size of maximum clique in $G$. I think the following inequality holds:
$$
\omega(G)\leq bw(G)
$$
Intuition: Assume (in reverse of ...

**5**

votes

**1**answer

341 views

### A claim from “Graph minors - a survey” by Robertson and Seymour

Can someone give me a proof sketch for this:
Let $\mathscr{P}_n$ be the set of all graphs which do not contain a path on $n$ vertices as a subgraph. Define the type of a graph inductively as: the type ...

**1**

vote

**1**answer

166 views

### Are there good ways of relating a minor to the full determinant?

Say $A$ is a $(n-1)\times (n-1)$ matrix and we augment it by a $n^{th}$ row and a column and get a $n \times n$ matrix $B$. Is there a nice way to relate $det(B)$ and $det(A)$ and the added row and ...

**7**

votes

**2**answers

302 views

### Number of edges in linklessly embeddable graphs

What is the maximum number of edges of an $n$-vertex linklessly embeddable graph?
A more general question is the following. What is the maximum number of edges of an $n$-vertex graph with Colin de ...

**3**

votes

**1**answer

200 views

### Contracting a planar graph to a (multiply-edged)-tree

Given a planar graph (no loops, no multiple edge), is it always possible to perform edge contractions* in order to obtain a graph $T$ which has no loops, and if one ignores parallel edges, $T$ is a ...

**2**

votes

**1**answer

279 views

### A variant of Kruskal's theorem

For $X$ and $Y$ finite sequences of finite trees, let us say that $X$ is everywhere contained in $Y$ ($X\subseteq_{ec}Y$) iff, for every $y\in Y$, there is some $x\in X$ such that $x$ is a minor of $y$...

**4**

votes

**1**answer

270 views

### Do graphs with large number of paths contain large chain minor?

Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge.
Note that the number of paths between two endpoints of a $k$-chain is $2^k.$
Question: Let $G$...

**4**

votes

**2**answers

435 views

### Do graphs with large number of cycles always contain large necklace minor?

Let "$k$-necklace" denote the (multi)graph obtained from a cycle of length $k$ by duplicating every edge.
Note that the number of cycles in $k$-necklace is at least $2^k.$
Question : Suppose a ...

**3**

votes

**1**answer

657 views

### Big binary tree as an induced subgraph

I believe this is true:
Suppose $G$ is a graph. If $G$ has a subdivision of a large binary tree, prove that $G$ has an
induced subgraph which is a subdivision of a large binary tree or the line ...