Weaker Version Of Hadwiger's Conjecture

155 Views Asked by At

Hadwiger's Conjecture states that if we have a graph $G$ with chromatic number $k$, then $G$ contains $K_k$ as a minor.

My question is, is it already known that there is some finite list of graphs $\lbrace H_1, ..., H_n \rbrace $ such that if $G$ has chromatic number $k$, then $G$ contains some $H_i$ as a minor?

1

There are 1 best solutions below

0
On

The short answer is yes absolutely, but there a lot of meaningless examples guaranteed by chromatic index(paths, cycles, $k$-partite graphs), and meaningful examples redirect to Hadwider's. If $G$ has chromatic index $k$ then $G$ has a minor in $\{K_1,K_2,K_3\}$, $i=k$ or $k\ge 3 \Rightarrow i=3$. The 4 color theorem being true independently of Hadwiger's includes $K_5$ in the set of minors, similarly. Other theorems can include $K_n, n<k$. Minor finding in general is a big topic, but if the question is about minor finding based on the chromatic index, we are almost exclusively looking for complete graphs, and Hadwiger's is as tight as the question will ever be.

If the question is about something other than the chromatic index, the minors guaranteed and forbidden get more diverse and more researchable. Forbidden and guaranteed minors associated with the genus of a graph is arguably a bigger open problem. It also looks more like the question you are asking...