Sphere Representations, Stacked Polytopes, and the Colin de Verdière Number of a GraphThe Electronic Journal of Combinatorics
AbstractWe 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.
Document VersionPublished Version
CopyrightCopyright © 2016, Authors
PublisherElectronic Journal of Combinatorics
Citation InformationLon Mitchell and Lynne Yengulalp. "Sphere Representations, Stacked Polytopes, and the Colin de Verdière Number of a Graph" The Electronic Journal of Combinatorics Vol. 23 Iss. 1 (2016)
Available at: http://works.bepress.com/lynne_yengulalp/4/