Structural properties of recursively partitionable graphs with connectivity 2. (English) Zbl 1400.05197

Summary: A connected graph \(G\) is said to be arbitrarily partitionable (AP for short) if for every partition \((n_1,\dots, n_p)\) of \(|V(G)|\) there exists a partition \((V_1,\dots, V_p)\) of \(V(G)\) such that each \(V_i\) induces a connected subgraph of \(G\) on \(n_i\) 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.


05C75 Structural characterization of families of graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI


[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 · Zbl 1002.68107
[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 · Zbl 1092.05054
[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 · Zbl 1300.05245
[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 · Zbl 1234.05182
[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 · Zbl 1259.05135
[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 · Zbl 1276.05064
[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 · Zbl 1179.05089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.