Geodesic
Structural Properties of Recursively Partitionable Graphs with Connectivity 2
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 89-115.

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

A connected graph G is said to be arbitrarily partitionable (AP for short) if for every partition (n1, . . ., np) of |V (G)| there exists a partition (V1, . . ., Vp) of V (G) such that each Vi induces a connected subgraph of G on ni vertices. Some stronger versions of this property were introduced, namely the ones of being online arbitrarily partitionable and recursively arbitrarily partitionable (OL-AP and R-AP for short, respectively), in which the subgraphs induced by a partition of G must not only be connected but also fulfil additional conditions. In this paper, we point out some structural properties of OL-AP and R-AP graphs with connectivity 2. In particular, we show that deleting a cut pair of these graphs results in a graph with a bounded number of components, some of whom have a small number of vertices. We obtain these results by studying a simple class of 2-connected graphs called balloons.
Keywords: online arbitrarily partitionable graph, recursively arbitrarily partitionable graph, graph with connectivity 2, balloon graph 
@article{DMGT_2017_37_1_a7,
     author = {Baudon, Olivier and Bensmail, Julien and Foucaud, Florent and Pil\'sniak, Monika},
     title = {Structural {Properties} of {Recursively} {Partitionable} {Graphs} with {Connectivity} 2},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {89--115},
     publisher = {mathdoc},
     volume = {37},
     number = {1},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a7/}
}
TY  - JOUR
AU  - Baudon, Olivier
AU  - Bensmail, Julien
AU  - Foucaud, Florent
AU  - Pilśniak, Monika
TI  - Structural Properties of Recursively Partitionable Graphs with Connectivity 2
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 89
EP  - 115
VL  - 37
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a7/
LA  - en
ID  - DMGT_2017_37_1_a7
ER  - 
%0 Journal Article
%A Baudon, Olivier
%A Bensmail, Julien
%A Foucaud, Florent
%A Pilśniak, Monika
%T Structural Properties of Recursively Partitionable Graphs with Connectivity 2
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 89-115
%V 37
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a7/
%G en
%F DMGT_2017_37_1_a7
Baudon, Olivier; Bensmail, Julien; Foucaud, Florent; Pilśniak, Monika. Structural Properties of Recursively Partitionable Graphs with Connectivity 2. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 89-115. http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a7/

[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] O. Baudon, F. Foucaud, J. Przyby lo and M. Woźniak, On the structure of arbitrarily partitionable graphs with given connectivity, Discrete Appl. Math. 162 (2014) 381–385. doi:10.1016/j.dam.2013.09.007

[4] O. Baudon, F. Gilbert and M. Woźniak, Recursively arbitrarily vertex-decomposable suns, Opuscula Math. 31 (2011) 533–547. doi:10.7494/OpMath.2011.31.4.533

[5] O. Baudon, F. Gilbert and M. Woźniak, Recursively arbitrarily vertex-decomposable graphs, Opuscula Math. 32 (2012) 689–706. doi:10.7494/OpMath.2012.32.4.689

[6] J. Bensmail, On the longest path in a recursively partitionable graph, Opuscula Math. 33 (2013) 631–640. doi:10.7494/OpMath.2013.33.4.631

[7] S. Cichacz, A. Görlich, A. Marczyk, J. Przyby lo and M. Woźniak, Arbitrarily vertex decomposable caterpillars with four or five leaves, Discuss. Math. Graph Theory 26 (2006) 291–305. doi:10.7151/dmgt.1321

[8] R. Diestel, Graph Theory (Springer, Berlin Heidelberg, 2005).

[9] E. Győri, On division of graphs to connected subgraphs, in: Combinatorics, Proc. Fifth Hungariam Colloq., Keszthely, 1976, Vol. I, Colloq. Math. Soc. János Bolyai 18 (1978) 485–494.

[10] M. Horňák, Zs. Tuza and M. Woźniak, On-line arbitrarily vertex decomposable trees, Discrete Appl. Math. 155 (2007) 1420–1429. doi:10.1016/j.dam.2007.02.011

[11] M. Horňák and M. Woźniak, Arbitrarily vertex decomposable trees are of maximum degree at most six, Opuscula Math. 23 (2003) 49–62.

[12] L. Lovász, A homology theory for spanning trees of a graph, Acta Math. Hungar. 30 (1977) 241–251.

[13] A. Marczyk, An Ore-type condition for arbitrarily vertex decomposable graphs, Discrete Math. 309 (2009) 3588–3594. doi:10.1016/j.disc.2007.12.066