Document Type

Article

Publication Date

2016

Publication Source

The Electronic Journal of Combinatorics

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

Volume

23

Issue

1

Volume

23

Issue

1

Peer Reviewed

yes


Share

COinS