Coloring Minimal Cayley Graphs

主 讲 人 ：Kolja Knauer    研究员

活动时间：09月11日14时00分    

地      点 ：理科群1号楼D203室

讲座内容：

A Cayley graph Cay(G,C) of a finite group G is called minimal if C is an inclusion-minimal generating set of G. In the 70s, Laszlo Babai posed a strong conjecture that would imply that all minimal Cayley graphs have chromatic number bounded by a global constant. We show that indeed for nilpotent and generalized dihedral groups such a constant exists - all minimal Cayley graphs of such groups can be colored with 3 colors. On the other hand we disprove the strong conjecture of Babai. Whether all minimal Cayley graphs have constant chromatic number remains open.

主讲人介绍：

Kolja Knauer received his PhD 2010 in Berlin, has published over 70 papers, and two books and is editor-in-chief of Annals of Combinatorics. He currently holds a position at Universitat de Barcelona and is a visiting professor at Hebei Normal University.

发布时间：2024-09-11 08:28:11