Geodesic
A partition of connected graphs
The electronic journal of combinatorics, Tome 12 (2005)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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$.
DOI : 10.37236/1968
Classification : 05C30, 05C05, 05C75
Mots-clés : tree, graph invariants, chromatic polynomial 
@article{10_37236_1968,
     author = {Gus Wiseman},
     title = {A partition of connected graphs},
     journal = {The electronic journal of combinatorics},
     year = {2005},
     volume = {12},
     doi = {10.37236/1968},
     zbl = {1060.05048},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1968/}
}
TY  - JOUR
AU  - Gus Wiseman
TI  - A partition of connected graphs
JO  - The electronic journal of combinatorics
PY  - 2005
VL  - 12
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1968/
DO  - 10.37236/1968
ID  - 10_37236_1968
ER  - 
%0 Journal Article
%A Gus Wiseman
%T A partition of connected graphs
%J The electronic journal of combinatorics
%D 2005
%V 12
%U http://geodesic.mathdoc.fr/articles/10.37236/1968/
%R 10.37236/1968
%F 10_37236_1968
Gus Wiseman. A partition of connected graphs. The electronic journal of combinatorics, Tome 12 (2005). doi: 10.37236/1968

Cité par Sources :