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
3 votes
2 answers
105 views

Let $G$ be a graph of genus $g$. Is the number of (non necessarily disjoint) 5-clique subgraphs at most $f(g)$ for some function $f$?

For a graph of genus $g$, it holds that it cannot have too many disjoint 5-cliques, as each clique requires a new handle. It feels that given a graph of genus $g$, it cannot have an unbounded number ...
master bob's user avatar
2 votes
1 answer
80 views

A reference for Wagner's Theorem

In the course of a project I am developing I have to use a classical result in topological graph theory due to Wagner in which Wagner gives the precise structure of graphs in which $K_5$ is excluded ...
Johnny Cage's user avatar
  • 1,543
6 votes
0 answers
223 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 homomorphisms from graphs $H$ such that $K_k$ is a minor of $H$ without needing to do any vertex deletions, only edge ...
Sean Longbrake's user avatar
0 votes
0 answers
78 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 ...
Xin Zhang's user avatar
  • 1,130
0 votes
1 answer
100 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 ${\...
Dominic van der Zypen's user avatar
3 votes
1 answer
125 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 ...
modnar's user avatar
  • 133
1 vote
1 answer
126 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,...
Rouhollah Mofid's user avatar
0 votes
0 answers
26 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$...
Hao S's user avatar
  • 161
0 votes
0 answers
60 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\...
Dominic van der Zypen's user avatar
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 ...
Agelos's user avatar
  • 1,844
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 ...
Dominic van der Zypen's user avatar
1 vote
0 answers
57 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 ...
Dominic van der Zypen's user avatar
6 votes
1 answer
452 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 ...
okw1124's user avatar
  • 331
5 votes
1 answer
423 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$. ...
Tri's user avatar
  • 1,366
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 ...
ben macintosh's user avatar
4 votes
0 answers
66 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 ...
Dominic van der Zypen's user avatar
1 vote
0 answers
106 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 ...
Dominic van der Zypen's user avatar
4 votes
0 answers
361 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$ ...
monkeymaths's user avatar
  • 1,169
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$...
Dominic van der Zypen's user avatar
1 vote
0 answers
75 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 ...
Dominic van der Zypen's user avatar
6 votes
1 answer
561 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 ...
Ethan Splaver's user avatar
5 votes
2 answers
407 views

Forbidden minors of a graph with treewidth at most 4

I am interested in the graphs with treewidth 5 because of their relationship with the realization dimension of a graph (see here). In this PhD thesis, 75 minimal forbidden minors of graphs with ...
Ryoshun Oba's user avatar
4 votes
0 answers
263 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 ...
Emre Yolcu's user avatar
4 votes
1 answer
172 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 ...
user62562's user avatar
  • 399
3 votes
0 answers
48 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 ...
Lior Gishboliner's user avatar
6 votes
1 answer
498 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 ...
Stella Biderman's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
10 votes
2 answers
410 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?
Arshak Aivazian's user avatar
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$ ...
Dominic van der Zypen's user avatar
6 votes
0 answers
173 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$ ...
user21820's user avatar
  • 2,734
4 votes
0 answers
92 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 ...
GMB's user avatar
  • 1,379
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 ...
user137930's user avatar
6 votes
2 answers
505 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 ...
domotorp's user avatar
  • 18.3k
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 ...
Dominic van der Zypen's user avatar
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 ${\...
Dominic van der Zypen's user avatar
2 votes
0 answers
54 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 ...
Herng Yi's user avatar
  • 221
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 ${\...
Dominic van der Zypen's user avatar
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$ ...
Dominic van der Zypen's user avatar
11 votes
3 answers
401 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 ...
monkeymaths's user avatar
  • 1,169
3 votes
0 answers
134 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,\...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
0 votes
1 answer
117 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 ...
Dominic van der Zypen's user avatar
1 vote
1 answer
239 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\...
Turbo's user avatar
  • 13.6k
1 vote
0 answers
119 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 ...
Christopher King's user avatar
6 votes
1 answer
332 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 ...
delete000's user avatar
  • 163
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 $...
Dominic van der Zypen's user avatar
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{...
Dominic van der Zypen's user avatar
-2 votes
1 answer
131 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, ...
Dominic van der Zypen's user avatar
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}$ ...
Dominic van der Zypen's user avatar