Even Maps, the Colin de Verdiere Number and Representations of Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10476095" target="_blank" >RIV/00216208:11320/22:10476095 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=n1-X1aHe-f" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=n1-X1aHe-f</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00493-021-4443-7" target="_blank" >10.1007/s00493-021-4443-7</a>
Alternative languages
Result language
angličtina
Original language name
Even Maps, the Colin de Verdiere Number and Representations of Graphs
Original language description
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) <= sigma(G) + 2 and conjectured sigma(G) <= sigma(G) for any graph G. We confirm this conjecture. As far as we know, this is the first topological upper bound on sigma(G) which is, in general, tight. Equality between mu and sigma does not hold in general as van der Holst and Pendavingh showed that there is a graph G with mu(G) <= 18 and sigma(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).
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
<a href="/en/project/GJ19-04113Y" target="_blank" >GJ19-04113Y: Advanced tools in combinatorics, topology and related areas</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Combinatorica
ISSN
0209-9683
e-ISSN
1439-6912
Volume of the periodical
42
Issue of the periodical within the volume
SUPPL 2 / Supplement 2
Country of publishing house
DE - GERMANY
Number of pages
29
Pages from-to
1317-1345
UT code for WoS article
000798210100003
EID of the result in the Scopus database
2-s2.0-85130418329