Skip to main content
Col(G) \geq \chi(G)
Source Link

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 $\text{Col}(G)\leq \chi(G)$$\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)$?

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 $\text{Col}(G)\leq \chi(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)$?

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

Source Link

Hadwiger's conjecture for coloring number instead of chromatic number

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 $\text{Col}(G)\leq \chi(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)$?