The Hadwiger number of a graph , denoted , is the largest integer such that contains as a minor. A famous conjecture due to Hadwiger in 1943 states that for every graph , , where denotes the chromatic number of . Let denote the independence number of . A graph is -free if it does not contain the graph as an induced subgraph. In 2003, Plummer, Stiebitz and Toft proved that for all -free graphs with , where is any graph on four vertices with , , or is a particular graph on seven vertices. In 2010, Kriesell considered a particular strengthening of Hadwiger’s conjecture due to Seymour and subsequently generalized the statement to include all forbidden subgraphs on five vertices with . In this note, we prove that $h(G) \ge \chi(G)W_5G\alpha(G) \le 2W_5$ denotes the wheel on six vertices.

生成讲解博客的中文版本

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