All Questions
Tagged with hadwiger-conjecture graph-theory
10 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
3
votes
0
answers
227
views
A form of Hadwiger's conjecture for hypergraphs
A hypergraph $H=(V,E)$ consists of a
set $V$ and $E\subseteq {\mathcal P}(V)$. If $S\subseteq V$, we define
$$E|_S = \{e\cap S: (e\in E) \land (e\cap S \neq \emptyset)\}$$
and call $(S, E|_S)$ the ...
- 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
5
votes
1
answer
579
views
Does the weak Hadwiger conjecture imply the Hadwiger conjecture?
For any cardinal $\kappa$, let $K_\kappa$ denote the complete graph on $\kappa$. We consider the following statements:
(H) If $G$ is a graph and $\chi(G) = \kappa$ then $K_\kappa$ is a minor of $G$.
...
- 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