Skip to main content
Article
Sphere Representations, Stacked Polytopes, and the Colin de Verdière Number of a Graph
The Electronic Journal of Combinatorics
  • Lon Mitchell, American Mathematical Society
  • Lynne Yengulalp, University of Dayton
Document Type
Article
Publication Date
1-1-2016
Abstract
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.
Inclusive pages
1-11
ISBN/ISSN
1077-8926
Document Version
Published Version
Comments

This document is provided for download in compliance with the publisher's policy for self-archiving. Permission documentation is on file.

Publisher
Electronic Journal of Combinatorics
Peer Reviewed
Yes
Citation Information
Lon 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/