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

Improve this question
$\endgroup$
2
  • $\begingroup$ Yes - thanks for noticing! Just corrected my mistake $\endgroup$
    – Dominic van der Zypen
    Commented 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$
    – David Eppstein
    Commented Feb 25, 2015 at 19:25

1 Answer 1

Reset to default
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$).

Improve this answer
$\endgroup$

You must log in to answer this question.

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