Geodesic
Arbitrarily vertex decomposable caterpillars with four or five leaves
Discussiones Mathematicae. Graph Theory, Tome 26 (2006) no. 2, pp. 291-305.

Voir la notice de l'article provenant de la source Library of Science

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (a₁,...,aₖ) of positive integers such that a₁+...+aₖ = n there exists a partition (V₁,...,Vₖ) of the vertex set of G such that for each i ∈ 1,...,k, V_i induces a connected subgraph of G on a_i vertices. D. Barth and H. Fournier showed that if a tree T is arbitrarily vertex decomposable, then T has maximum degree at most 4. In this paper we give a complete characterization of arbitrarily vertex decomposable caterpillars with four leaves. We also describe two families of arbitrarily vertex decomposable trees with maximum degree three or four.
Keywords: arbitrarily vertex decomposable graphs, trees, caterpillars, star-like trees 
@article{DMGT_2006_26_2_a10,
     author = {Cichacz, Sylwia and G\"orlich, Agnieszka and Marczyk, Antoni and Przyby{\l}o, Jakub and Wo\'zniak, Mariusz},
     title = {Arbitrarily vertex decomposable caterpillars with four or five leaves},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {291--305},
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {2006},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2006_26_2_a10/}
}
TY  - JOUR
AU  - Cichacz, Sylwia
AU  - Görlich, Agnieszka
AU  - Marczyk, Antoni
AU  - Przybyło, Jakub
AU  - Woźniak, Mariusz
TI  - Arbitrarily vertex decomposable caterpillars with four or five leaves
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2006
SP  - 291
EP  - 305
VL  - 26
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2006_26_2_a10/
LA  - en
ID  - DMGT_2006_26_2_a10
ER  - 
%0 Journal Article
%A Cichacz, Sylwia
%A Görlich, Agnieszka
%A Marczyk, Antoni
%A Przybyło, Jakub
%A Woźniak, Mariusz
%T Arbitrarily vertex decomposable caterpillars with four or five leaves
%J Discussiones Mathematicae. Graph Theory
%D 2006
%P 291-305
%V 26
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2006_26_2_a10/
%G en
%F DMGT_2006_26_2_a10
Cichacz, Sylwia; Görlich, Agnieszka; Marczyk, Antoni; Przybyło, Jakub; Woźniak, Mariusz. Arbitrarily vertex decomposable caterpillars with four or five leaves. Discussiones Mathematicae. Graph Theory, Tome 26 (2006) no. 2, pp. 291-305. http://geodesic.mathdoc.fr/item/DMGT_2006_26_2_a10/

[1] D. Barth, O. Baudon and J. Puech, Decomposable trees: a polynomial algorithm for tripodes, Discrete Appl. Math. 119 (2002) 205-216, doi: 10.1016/S0166-218X(00)00322-X.

[2] D. Barth and H. Fournier, A degree bound on decomposable trees, Discrete Math. 306 (2006) 469-477, doi: 10.1016/j.disc.2006.01.006.

[3] M. Hornák and M. Woźniak, On arbitrarily vertex decomposable trees, Technical report, Faculty of Applied Mathematics, Kraków (2003), submitted.

[4] M. Hornák and M. Woźniak, Arbitrarily vertex decomposable trees are of maximum degree at most six, Opuscula Mathematica 23 (2003) 49-62.