All Questions
Tagged with graph-minors hadwiger-conjecture
8 questions
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.8k
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
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
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
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
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,976