5
$\begingroup$

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$.

(WH) If $G$ is a graph and there is no graph homomorphism $c: G\to K_\kappa$, then $K_\kappa$ is a minor of $G$.

For finite graphs, (H) is just Hadwiger's conjecture. It turns out that (H) is false for $\kappa \geq \aleph_0$: the disjoint union of all $K_\lambda$ where $\lambda < \kappa$ has chromatic number $\kappa$ but does not contain $K_\kappa$ as a minor.

However, (WH) is true for graphs $G$ with $\chi(G) \geq \aleph_0$ (see http://arxiv.org/pdf/1312.2829.pdf ). Let us call (WH) the Weak Hadwiger conjecture. In the finite case, (WH) translates to: "If $\chi(G) = n+1$ then $K_{n}$ is a minor of $G$." It is not known whether (WH) holds for finite graphs.

Question: Does (WH) imply (H) for finite graphs?

$\endgroup$

1 Answer 1

6
$\begingroup$

Well, it is possible that both (WH) and (H) are true, in which case (WH) implies (H).

If on the other hand, you are asking if there is a short proof of (H) assuming (WH), then the answer is no. For example, Hadwiger's Conjecture for $n=5$ says

If $G$ has no $K_5$-minor, then $\chi(G) \leq 4$,

while the Weak Hadwiger's Conjecture for $n=5$ says

If $G$ has no $K_5$-minor, then $\chi(G) \leq 5$.

By Wagner's characterization of $K_5$-minor free graphs, the first assertion is equivalent to the $4$-Colour Theorem, while the second assertion is equivalent to the $5$-Colour Theorem (every planar graph is $5$-colourable). So unless you think the $5$-Colour Theorem (which has an easy proof) implies the $4$-Colour Theorem (which is not known to have an easy proof), the answer is no.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .