The Electronic Journal of Combinatorics
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 R k+1. As a result, we derive lower bounds for Colin de Verdi`ere’s µ of complements of partial k-trees and prove that µ(G) + µ(G) > |G| − 2 for all chordal G.
Copyright © 2016, Authors
Electronic Journal of Combinatorics
Mitchell, Lon and Yengulalp, Lynne, "Sphere Representations, Stacked Polytopes, and the Colin de Verdière Number of a Graph" (2016). Mathematics Faculty Publications. 36.