All Questions
Tagged with graph-minors graph-theory
27 questions with no upvoted or accepted answers
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
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
6
votes
0
answers
271
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 ...
6
votes
0
answers
187
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$ ...
- 2,912
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
5
votes
0
answers
94
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 $...
- 48.8k
4
votes
0
answers
98
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,926
4
votes
0
answers
67
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 ...
- 48.8k
4
votes
0
answers
387
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$ ...
- 1,169
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
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
3
votes
0
answers
143
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,\...
- 48.8k
2
votes
0
answers
55
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$...
- 48.8k
2
votes
0
answers
58
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 ...
- 221
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
1
vote
0
answers
64
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 ...
- 48.8k
1
vote
0
answers
58
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 ...
- 48.8k
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 ...
1
vote
0
answers
114
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 ...
- 48.8k
1
vote
0
answers
78
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 ...
- 48.8k
1
vote
0
answers
41
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 ...
- 48.8k
1
vote
0
answers
38
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$ ...
- 48.8k
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
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
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,976
0
votes
0
answers
81
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 ...
- 1,190
0
votes
0
answers
61
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\...
- 48.8k