Even maps, the Colin de Verdière number and representations of graphs

Kaluza V, Tancer M. 2022. Even maps, the Colin de Verdière number and representations of graphs. Combinatorica.


Journal Article | Epub ahead of print | English
Department
Abstract
Van der Holst and Pendavingh introduced a graph parameter σ, which coincides with the more famous Colin de Verdière graph parameter μ for small values. However, the definition of a is much more geometric/topological directly reflecting embeddability properties of the graph. They proved μ(G) ≤ σ(G) + 2 and conjectured σ(G) ≤ σ(G) for any graph G. We confirm this conjecture. As far as we know, this is the first topological upper bound on σ(G) which is, in general, tight. Equality between μ and σ does not hold in general as van der Holst and Pendavingh showed that there is a graph G with μ(G) ≤ 18 and σ(G) ≥ 20. We show that the gap appears at much smaller values, namely, we exhibit a graph H for which μ(H) ≥ 7 and σ(H) ≥ 8. We also prove that, in general, the gap can be large: The incidence graphs Hq of finite projective planes of order q satisfy μ(Hq) ∈ O(q3/2) and σ(Hq) ≥ q2.
Publishing Year
Date Published
2022-05-19
Journal Title
Combinatorica
Acknowledgement
V. K. gratefully acknowledges the support of Austrian Science Fund (FWF): P 30902-N35. This work was done mostly while he was employed at the University of Innsbruck. During the early stage of this research, V. K. was partially supported by Charles University project GAUK 926416. M. T. is supported by the grant no. 19-04113Y of the Czech Science Foundation(GA ˇCR) and partially supported by Charles University project UNCE/SCI/004.
ISSN
IST-REx-ID

Cite this

Kaluza V, Tancer M. Even maps, the Colin de Verdière number and representations of graphs. Combinatorica. 2022. doi:10.1007/s00493-021-4443-7
Kaluza, V., & Tancer, M. (2022). Even maps, the Colin de Verdière number and representations of graphs. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-021-4443-7
Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number and Representations of Graphs.” Combinatorica. Springer Nature, 2022. https://doi.org/10.1007/s00493-021-4443-7.
V. Kaluza and M. Tancer, “Even maps, the Colin de Verdière number and representations of graphs,” Combinatorica. Springer Nature, 2022.
Kaluza V, Tancer M. 2022. Even maps, the Colin de Verdière number and representations of graphs. Combinatorica.
Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number and Representations of Graphs.” Combinatorica, Springer Nature, 2022, doi:10.1007/s00493-021-4443-7.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 1907.05055

Search this title in

Google Scholar