On the generalized Mycielskian of complements of odd cycles

Gujgiczer, Anna and Simonyi, Gábor and Tardos, Gábor (2023) On the generalized Mycielskian of complements of odd cycles. In: Proceedings of the 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications. Budapesti Műszaki és Gazdaságtudományi Egyetem, Villamosmérnöki és Informatikai Kar, Számítástudományi és Információelméleti Tanszék, Budapest, pp. 485-488. ISBN 9789634219033

Preview

Text kompcycgenmyc_final-1.pdf Download (199kB) | Preview

Abstract

The main goal of this talk is to popularize a (special case of a) result of Pan and Zhu according to which whether the generalized Mycielski construction applied to the complement C2k+1 of an odd cycle makes the chromatic number increase or not depends on the residue of 2k + 1 modulo 4. This surprizing phenomenon is explained by the topological properties of the circular complete graphs Kp/q and the trivial observation that C2k+1 is isomorphic to K(2k+1)/2.

Actions (login required)

Edit Item