7
$\begingroup$

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(G) \leq \eta(G)$ for every finite graph $G$.

A crude approximation "from below" for $\chi(G)$ is $|V(G)|/\alpha(G)$ where $\alpha(G)$ is the size of the largest independent set in $G$. We get $|V(G)|/\alpha(G) \leq \chi(G)$ because every coloring is a partition of $V(G)$ into independent sets.

Question. Is $|V(G)|/\alpha(G) \leq \eta(G)$ for all finite graphs $G$?

$\endgroup$
3
  • 3
    $\begingroup$ Not sure about the state of the art, but there are some approximation results, see e.g. web.math.princeton.edu/~pds/papers/hadwiger/paper.pdf section 4. $\endgroup$
    – 1001
    Commented May 13 at 21:46
  • 2
    $\begingroup$ to my memory the bound of Balogh and Kostochka quoted in this Seymour paper remain the state of the art. $\endgroup$ Commented May 15 at 3:32
  • 1
    $\begingroup$ Please use a high-level tag like "co.combinatorics". I added this tag now. Regarding high-level tags, see meta.mathoverflow.net/q/1075 $\endgroup$
    – GH from MO
    Commented May 17 at 4:54

1 Answer 1

4
$\begingroup$

This weakening is still an open question, even in the very special case of graphs with $\alpha(G)=2$ (complements of triangle-free graphs). In other words, do all graphs with independence number two (or "stability number" two in older literature) have a $K_{\lceil n/2 \rceil}$ minor? See Open Question 4.8 in Paul Seymour's survey and the comments around it, in particular:

This seems to me to be an excellent place to look for a counterexample. My own belief is, if it is true for graphs with stability number two then it is probably true in general, so it would be very nice to decide this case.

Since that survey (2016), there's been a few results in that direction, but still no proof, see Dense minors of graphs with independence number two (2022) by Sergey Norin and Paul Seymour and papers that cite it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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