3
$\begingroup$

For any graph $G=(V,E)$, the coloring number $\text{Col}(G)$ is defined to be the smallest cardinal $\kappa$ such that there is a well-ordering $\leq$ on $V$ such that for every vertex $v\in V$ we have $$|N(v) \cap \{w\in V: w \leq v\}| \leq \kappa,$$ where $N(v)=\{x\in V:\{x,v\}\in E(G)\}$.

It is known that $\chi(G) \leq \text{Col}(G)$ for all graphs $G$.

The Hadwiger number $\eta(G)$ of a finite graph $G$ is the largest integer $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$. Hadwiger's conjecture states that $\chi(G)\leq \eta(G)$ for all finite graphs.

Question: Is there a finite graph $G$ such that $\eta(G) < \text{Col}(G)$?

$\endgroup$
2
  • $\begingroup$ Yes - thanks for noticing! Just corrected my mistake $\endgroup$ Feb 25, 2015 at 16:24
  • 1
    $\begingroup$ I think there's an off-by-one in your definition of Col; for instance, the chromatic number of a path is two, its coloring number should also be two, but you show it as one (violating the claimed inequality between chromatic number and coloring number). arxiv.org/abs/1101.2630 looks relevant but because it's about immersions rather than minors it doesn't answer your question. $\endgroup$ Feb 25, 2015 at 19:25

1 Answer 1

4
$\begingroup$

Take the complete 3-partite graph $K_{n,n,n}$. Coloring number $2n+1$ (with the correct +1 definition). Any $K_{2n+1}$ minor would have to have at least $n+1$ singleton branch sets, i.e. there would be a $K_{n+1}$ subgraph (which is not there for $n\ge 3$).

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