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)$?

  • $\begingroup$ Yes - thanks for noticing! Just corrected my mistake $\endgroup$ – Dominic van der Zypen Feb 25 '15 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$ – David Eppstein Feb 25 '15 at 19:25

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

| cite | improve this answer | |

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.