All Questions
36 questions
5
votes
1
answer
409
views
4-color theorem for hypergraphs
Question. Does every hypergraph that does not admit a complete minor with $5$ elements have a coloring with $4$ colors?
Below are the definitions to make this precise.
If $H = (V, E)$ is a hypergraph ...
- 48.9k
0
votes
1
answer
80
views
Infinite complete minor in $\min,\max$-graph on $\mathbb{N}$
Let $[\omega]^2 =\big\{\{x,y\}:x\neq y \in \omega\big\}$ denote the collection of all 2-element subsets of the non-negative integers. Let $$E=\big\{\{p,q\} : p,q \in [\omega]^2 \text{ and } \max(p)=\...
- 48.9k
7
votes
1
answer
165
views
$|G|/\alpha(G) \leq \eta(G)$ where $\eta(G)$ is the Hadwiger number
Let $G=(V,E)$ be a finite, simple, undirected graph. The Hadwiger number $\eta(G)$ is the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$.
Hadwiger's celebrated conjecture states that $\chi(...
- 48.9k
1
vote
1
answer
130
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,...
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
6
votes
1
answer
566
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 ...
- 341
5
votes
1
answer
429
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$.
...
- 1,644
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.9k
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.9k
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
10
votes
2
answers
433
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?
- 6,962
6
votes
0
answers
188
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
1
answer
295
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 ...
- 95
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$ ...
- 48.9k
11
votes
3
answers
409
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 ...
- 1,169
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.9k
6
votes
1
answer
341
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 ...
- 163
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.9k
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{...
- 48.9k
-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, ...
- 48.9k
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
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
4
votes
0
answers
184
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.9k
2
votes
1
answer
252
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 ...
- 311
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)$?
- 48.9k
5
votes
1
answer
274
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 ...
- 311
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 ...
user76479
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
2
votes
1
answer
181
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 ...
- 241
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 ...
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$...
- 197
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
7
votes
2
answers
827
views
Graph minor check
Are there any good algebraic/algorithmic tools available to check if a given graph $H$ is a minor of $G$ from the adjacency matrix of $G$?
- 13.9k
46
votes
8
answers
5k
views
Can a problem be simultaneously polynomial time and undecidable?
The Robertson-Seymour theorem on graph minors leads to some interesting conundrums.
The theorem states that any minor-closed class of graphs can be described by a finite number of excluded minors. As ...
- 12.7k
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 ...
- 1,180