Even maps, the Colin de Verdière number and representations of graphs
Kaluza, Vojtech
Tancer, Martin
ddc:514
ddc:516
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.
Springer Nature
2022
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.ista.ac.at/record/10335
Kaluza V, Tancer M. Even maps, the Colin de Verdière number and representations of graphs. <i>Combinatorica</i>. 2022;42:1317-1345. doi:<a href="https://doi.org/10.1007/s00493-021-4443-7">10.1007/s00493-021-4443-7</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/s00493-021-4443-7
info:eu-repo/semantics/altIdentifier/issn/0209-9683
info:eu-repo/semantics/altIdentifier/wos/000798210100003
info:eu-repo/semantics/altIdentifier/arxiv/1907.05055
info:eu-repo/semantics/openAccess