Geodesic
A partition of connected graphs
The electronic journal of combinatorics, Tome 12 (2005)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv EuDML
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 
Gus Wiseman. A partition of connected graphs. The electronic journal of combinatorics, Tome 12 (2005). doi: 10.37236/1968
@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

Cité par Sources :