Publikace na Matematicko-fyzikální fakulta |
2020
Abstrakt
Van der Holst and Pendavingh introduced a graph parameter sigma, which coincides with the more famous Cohn de Verdiere graph parameter mu for small values. However, the definition of sigma is much more geometric/topological directly reflecting embeddability properties of the graph.
They proved mu(G) = 20. We show that the gap appears on much smaller values, namely, we exhibit a graph H for which mu(H) = 8.
We also prove that, in general, the gap can be large: The incidence graphs H-q of finite projective planes of order q satisfy mu(H-q) is an element of O(q(3/2)) and sigma(H-q) >= q(2).