A partition of connected graphs (Q1773211)

Summary: 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 \(x^q\) in the chromatic polynomial \(\chi_G(x)\) 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\).