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.
87 questions
6
votes
2
answers
758
views
Minor-closed classes of graphs with large numbers of excluded minors
Robertson and Seymour tell us that any minor-closed family of graphs has a finite collection of excluded minors.
Standard examples include planar graphs with two excluded minors ($K_5$ and $K_{3,3}$) ...
- 4,713
0
votes
1
answer
133
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 ...
- 14k
0
votes
1
answer
125
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 ...
- 48.8k
1
vote
1
answer
255
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\...
- 13.9k
1
vote
0
answers
127
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,353
2
votes
1
answer
86
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{...
- 6,282
-2
votes
1
answer
138
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, ...
- 24.8k
4
votes
0
answers
220
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}$ ...
- 48.8k
1
vote
0
answers
1k
views
About Hadwiger's conjecture
Reading the Wikipedia article about Hadwiger's conjecture, I found this open problem really interesting. In this article it is written that
"in a minimal $k$-coloring of any graph $G$, contracting ...
- 6,051
6
votes
1
answer
124
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 — ...
- 2,966
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)$...
- 5,590
4
votes
0
answers
183
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 ...
- 48.8k
7
votes
2
answers
379
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 ...
- 32.1k
2
votes
3
answers
301
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)$?
- 32.1k
-1
votes
1
answer
52
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 ...
- 761
2
votes
1
answer
189
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)$
?
- 490
8
votes
1
answer
194
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 ...
- 6,101
2
votes
1
answer
132
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}$...
- 48.8k
1
vote
2
answers
188
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).
- 6,051
4
votes
1
answer
241
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 ...
- 32.1k
2
votes
0
answers
59
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, ...
- 311
6
votes
1
answer
128
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 ...
- 18.6k
21
votes
3
answers
2k
views
Obstructions for embedding a graph on a surface of genus g
Kuratowski's theorem tells us the complete graph $K_5$ and the bipartite graph $K_{3,3}$ are the only obstructions to a graph being planar, ie embeddable in the plane with no edge-crossings.
Is the ...
- 32.1k
1
vote
0
answers
85
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 ...
- 220
4
votes
2
answers
266
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 ...
CommunityBot
- 1
3
votes
1
answer
401
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 ...
- 311
9
votes
0
answers
499
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-...
- 1,169
3
votes
1
answer
171
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.
- 12.7k
5
votes
1
answer
400
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 ...
- 105k
2
votes
1
answer
221
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 ...
- 52.3k
3
votes
1
answer
679
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 ...
- 625
2
votes
1
answer
302
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$...
- 236
4
votes
2
answers
458
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 ...
CommunityBot
- 1
4
votes
1
answer
312
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$...
CommunityBot
- 1
6
votes
0
answers
151
views
Upper bound on size of obstruction set for wye-delta-wye reducible graphs
A graph is $Y \Delta Y$-reducible if it can be reduced to an empty graph by the following operations:
$Y \leftrightarrow\Delta$ transforms;
Replacing multiple edges with single edges (parallel ...
- 12.4k
26
votes
0
answers
657
views
Planar minor graphs
The theorem of Robertson-Seymour about graph minors says that there exists no infinite family of graphs such that none of them is a minor of another one.
Apparently, it came as a generalization of ...
- 1,875
5
votes
1
answer
392
views
Ref request: A graph G contains H as a minor iff it contains one of finitely many graphs as a topological minor
For definitions of graph minors and topological minors, see wikipedia's article on graph minors.
Theorem: For every graph H, there is a finite set of graphs, say S(H), such that G contains H as a ...
- 1,654