Questions tagged [hadwiger-conjecture]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
92 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 ...
4
votes
0answers
204 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}$ ...
6
votes
1answer
395 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$. ...
1
vote
0answers
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 ...