Faculty Publications

Title

Sphere Representations, Stacked Polytopes, and the Colin de Verdière Number of a Graph

SelectedWorks Author Profiles:

Lon Mitchell

Document Type

Article

Publication Date

2016

ISSN

1077-8926

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ère's μ of complements of partial k -trees and prove that μ ( G ) + μ ( ¯¯¯¯ G ) ≥ | G | − 2 for all chordal G .

Publisher

The Electronic Journal of Combinatorics

Share

COinS