Publication at Faculty of Mathematics and Physics |
2022
Abstract
Van der Holst and Pendavingh introduced a graph parameter sigma, which coincides with the more famous Colin de Verdiere graph parameter mu for small values. However, the definition of a is much more geometric/topological directly reflecting embeddability properties of the graph.
They proved mu(G) = 20. We show that the gap appears at much smaller values, namely, we exhibit a graph H for which mu(H) >= 7 and sigma(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).