Given a graph , the Hadwiger number of , denoted by , is the largest integer such that contains the complete graph as a minor. A hole in is an induced cycle of length at least four. Hadwiger’s Conjecture from 1943 states that for every graph , , where denotes the chromatic number of . In this paper we establish more evidence for Hadwiger’s conjecture by showing that if a graph with independence number has no hole of length between and , then . We also prove that if a graph with independence number has no hole of length between and , then contains an odd clique minor of size , that is, such a graph satisfies the odd Hadwiger’s conjecture.

生成讲解博客的中文版本

生成AI智能校验的中文版本