FROM THE MYCIELSKI CONSTRUCTION TO QUANTUM TWINS

Graph theory is not only of great importance in mathematics, but also has an enormous number of applications in other branches of science. In particular, it is a key ingredient in modeling noisy communication channels. Due to the recent extensive growth of interest in quantum information theory, the need for quantum analogs of classical graphs arose. The theory of quantum graphs and their (quantum) characteristics becomes a source of intriguing questions. One of the famous problems in classical graph theory was to verify if there exists a triangle-free graph of arbitrarily large chromatic number. The affirmative answer was provided by Mycielski, who proposed an explicit construction that transforms a given graph into a larger one without changing its clique number but enlarging the chromatic number by one. We generalize this transformation into the quantum world, study how it affects (quantum) characteristics of quantum graphs, and find relations between the quantum automorphism groups of the original graph and its Mycielskian. The latter problem led us to the concept of quantum twins and the study of their properties. Based on joint work with P. Kasprzak (arXiv:2306.09994) and work in progress with P. Kasprzak, P. M. Sołtan, and I. Chełstowski.