Skip to main content
Became Hot Network Question
edited title
Link

conjecture Conjecture of van der Holst and Pendavingh related to bound for Colin de Verdière invariant

added graph theory and spectral graph theory tag
Link
Claus
  • 6.9k
  • 4
  • 25
  • 45
Source Link

conjecture of Holst and Pendavingh related to bound for Colin de Verdière invariant

In their 2009 paper (“On a graph property generalizing planarity and flatness”. In: Combinatorica 29.3 (May 2009), pp. 337–361. issn: 1439-6912. doi: 10.1007/s00493-009-2219-6.), van der Holst and Pendavingh defined a new minor monotone graph invariant $\sigma(G)$ for a graph $G$: the minimal integer $k$ such that every CW-complex whose 1-skeleton is $G$ admits a certain even mapping into $\mathbb R^k$.

They were able to prove $\mu(G)\leq\sigma(G)+2$, where $\mu(G)$ is the Colin de Verdière number of $G$ which is minor monotone as well (Colin de Verdière. “Sur un nouvel invariant des graphes et un critère de planaritè”. In: Journal of Combinatorial Theory, Series B 50.1 (1990), pp. 11–21. issn: 0095-8956. doi: 10.1016/0095-8956(90)90093-F.)

My main interest is in the conjecture of van der Holst and Pendavingh in that paper. They conjectured that actually $\mu(G)\leq\sigma(G)$ might hold. Question: What is known about the status of this conjecture? (I have difficulties tracing it as their new invariant $\sigma(G)$ does not seem to have a commonly agreed name yet).