2005/05/09 by Gus Wiseman
Mathematics · #math.CO #msc:05C30 #msc:05C05
published as Electronic J. Combinatorics 12, N1 (2005), 8pp · 8 pages
arxiv created 2005/05/09 · arxiv updated 2009/12/01
We define an algorithm k which takes a connected graph G on a totally ordered vertex set and returns an increasing tree R (which is not necessarily a subtree of G). We characterize the set of graphs G such that k(G)=R. Because this set has a simple structure (it is isomorphic to a product of non-empty power sets), it is easy to evaluate certain graph invariants in terms of increasing trees. In particular, we prove that, up to sign, the coefficient of xq in the chromatic polynomial of G is the number of increasing forests with q components that satisfy a condition that we call G-connectedness. We also find a bijection between increasing G-connected trees and broken circuit free subtrees of G.