A partition of connected graphs
| dc.creator | Wiseman, Gus | |
| dc.date | 2005-05-09 | |
| dc.date.accessioned | 2026-07-07T05:19:44Z | |
| dc.date.available | 2026-07-07T05:19:44Z | |
| dc.description | 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 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. | |
| dc.description | 8 pages | |
| dc.identifier | https://arxiv.org/abs/math/0505155 | |
| dc.identifier | http://arxiv.org/abs/math/0505155 | |
| dc.identifier | Electronic J. Combinatorics 12, N1 (2005), 8pp | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/75124 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C30, 05C05 | |
| dc.title | A partition of connected graphs | |
| dc.type | text |