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.
88 questions
4
votes
1
answer
302
views
Translating the Hadwiger number of a graph $G$ to the clique number of another graph $\mathcal{H}(G)$
Graph $H$ is a minor of graph $G$ precisely when there exist pairwise disjoint sets of vertices $W_{u} \subseteq V(G)$ for every $u \in V(H)$ for which the subgraph induced on $W_u$ is connected and ...
- 191
0
votes
1
answer
145
views
Countable graph with $2^{\aleph_0}$ non-isomorphic induced minors
Let $G=(V,E)$ be a simple, undirected graph. If $S, T\subseteq V$ are disjoint sets, we say that $S,T$ are connected to each other if there are $s\in S, t\in T$ such that $\{s,t\}\in E$. We say a ...
- 56.5k
5
votes
1
answer
468
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 ...
- 56.5k
0
votes
1
answer
131
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)=\...
- 56.5k
7
votes
1
answer
211
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(...
- 56.5k
3
votes
2
answers
204
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 ...
- 31
2
votes
1
answer
149
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 ...
- 1,631
6
votes
0
answers
339
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 ...
0
votes
0
answers
108
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,220
0
votes
1
answer
151
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 ${\...
- 56.5k
3
votes
1
answer
171
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 ...
- 133
1
vote
1
answer
175
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,...
0
votes
0
answers
85
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\...
- 56.5k
4
votes
0
answers
135
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 ...
- 2,116
1
vote
0
answers
90
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 ...
- 56.5k