Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph (Q907257)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph |
scientific article |
Statements
Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph (English)
0 references
25 January 2016
0 references
Summary: We prove that a \(k\)-tree can be viewed as a subgraph of a special type of \((k+1)\)-tree that corresponds to a stacked polytope and that these ``stacked'' \((k+1)\)-trees admit representations by orthogonal spheres in \(\mathbb{R}^{k+1}\). As a result, we derive lower bounds for Colin de Verdière's \(\mu\) of complements of partial \(k\)-trees and prove that \(\mu(G) + \mu(\overline{G}) \geqslant |G| - 2\) for all chordal \(G\).
0 references
Colin de Verdière invariant
0 references
chordal graphs
0 references
sphere representations
0 references
stacked polytopes
0 references
0 references