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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
5 votes
1 answer
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 ...
user avatar
  • 321
5 votes
1 answer
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$. ...
user avatar
  • 1,064
1 vote
0 answers
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 ...
user avatar
4 votes
0 answers
61 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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
3 votes
0 answers
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$ ...
user avatar
  • 1,119
2 votes
0 answers
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$...
user avatar
1 vote
0 answers
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 ...
user avatar
6 votes
1 answer
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 ...
user avatar
  • 2,371
4 votes
2 answers
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 ...
user avatar
4 votes
0 answers
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 ...
user avatar
4 votes
1 answer
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 ...
user avatar
  • 399
3 votes
0 answers
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 ...
user avatar
5 votes
1 answer
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 ...
user avatar
1 vote
0 answers
27 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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
10 votes
2 answers
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?
user avatar
1 vote
0 answers
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$ ...
user avatar
6 votes
0 answers
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$ ...
user avatar
  • 2,649
4 votes
0 answers
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 ...
user avatar
  • 1,349
6 votes
1 answer
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 ...
user avatar
6 votes
2 answers
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 ...
user avatar
  • 17.2k
0 votes
1 answer
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 ...
user avatar
0 votes
1 answer
161 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 ${\...
user avatar
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 ...
user avatar
  • 221
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 ${\...
user avatar
2 votes
1 answer
90 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$ ...
user avatar
10 votes
3 answers
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 ...
user avatar
  • 1,119
3 votes
0 answers
123 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,\...
user avatar
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 ...
user avatar
0 votes
1 answer
97 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 ...
user avatar
1 vote
1 answer
211 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\...
user avatar
  • 13k
1 vote
0 answers
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 ...
user avatar
  • 4,160
6 votes
1 answer
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 ...
user avatar
  • 163
5 votes
0 answers
92 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 $...
user avatar
2 votes
1 answer
78 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{...
user avatar
-2 votes
1 answer
115 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, ...
user avatar
4 votes
0 answers
212 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}$ ...
user avatar
6 votes
1 answer
87 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 — ...
user avatar
0 votes
1 answer
42 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)$...
user avatar
-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 ...
user avatar
7 votes
1 answer
149 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 ...
user avatar
2 votes
1 answer
180 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)$ ?
user avatar
2 votes
1 answer
115 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}$...
user avatar
1 vote
2 answers
147 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).
user avatar
  • 311
2 votes
0 answers
57 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, ...
user avatar
  • 311
4 votes
0 answers
172 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 ...
user avatar
2 votes
1 answer
184 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 ...
user avatar
  • 311