加载中…
A graph is said to contain (a clique of size ) as a weak immersion if it has vertices, pairwise connected by edge-disjoint paths. In 1989, Lescure and Meyniel made the following conjecture related to Hadwiger’s conjecture: Every graph of chromatic number contains as a weak immersion. We prove this conjecture for graphs with at most vertices. As an application, we make some progress on Albertson’s conjecture, according to which every graph with chromatic number satisfies . In particular, we show that the conjecture is true for all graphs of chromatic number , provided that they have at most vertices.

生成讲解博客的中文版本

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