6
$\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$
7
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.