ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume


J. Bensmail

Julien Bensmail

Université Côte d'Azur



B. Li

Binlong Li



More aspects of arbitrarily partitionable graphs



Discussiones Mathematicae Graph Theory 42(4) (2022) 1237-1261

Received: 2020-03-09 , Revised: 2020-06-08 , Accepted: 2020-06-08 , Available online: 2020-07-15 ,


A graph $G$ of order $n$ is arbitrarily partitionable (AP) if, for every sequence $(n_1,\dots,n_p)$ partitioning $n$, there is a partition $(V_1,\dots,V_p)$ of $V(G)$ such that $G[V_i]$ is a connected $n_i$-graph for $i=1,\dots,p$. The property of being AP is related to other well-known graph notions, such as perfect matchings and Hamiltonian cycles, with which it shares several properties. This work is dedicated to studying two aspects behind AP graphs. On the one hand, we consider algorithmic aspects of AP graphs, which received some attention in previous works. We first establish the NP-hardness of the problem of partitioning a graph into connected subgraphs following a given sequence, for various new graph classes of interest. We then prove that the problem of deciding whether a graph is AP is in NP for several classes of graphs, confirming a conjecture of Barth and Fournier for these. On the other hand, we consider the weakening to APness of sufficient conditions for Hamiltonicity. While previous works have suggested that such conditions can sometimes indeed be weakened, we here point out cases where this is not true. This is done by considering conditions for Hamiltonicity involving squares of graphs, and claw- and net-free graphs.


arbitrarily partitionable graphs, partition into connected subgraphs, Hamiltonicity


  1. D. Barth, O. Baudon and J. Puech, Decomposable trees: a polynomial algorithm for tripodes, Discrete Appl. Math. 119 (2002) 205–216.
  2. D. Barth and H. Fournier, A degree bound on decomposable trees, Discrete Math. 306 (2006) 469–477.
  3. O. Baudon, J. Bensmail, F. Foucaud and M. Pilśniak, Structural properties of recursively partitionable graphs with connectivity $2$, Discuss. Math. Graph Theory 37 (2017) 89–115.
  4. O. Baudon, F. Gilbert and M. Woźniak, Recursively arbitrarily vertex-decomposable graphs, Opuscula Math. 32 (2012) 689–706.
  5. J. Bensmail, Partitions and decompositions of graphs, PhD. Thesis (Université de Bordeaux, France, 2014).
  6. J. Bensmail, On the complexity of partitioning a graph into a few connected subgraphs, J. Comb. Optim. 30 (2015) 174–187.
  7. J. Bensmail, On three polynomial kernels of sequences for arbitrarily partitionable graphs, Discrete Appl. Math. 202 (2016) 19–29.
  8. J.A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111–135.
  9. S. Brandt, Finding vertex decompositions in dense graphs (2013), personal communication.
  10. H. Broersma, D. Kratsch and G.J. Woeginger, Fully decomposable split graphs, European J. Combin. 34 (2013) 567–575.
  11. M. Dell'Amico and S. Martello, Reduction of the three-partition problem, J. Comb. Optim. 3 (1999) 17–30.
  12. M.E. Dyer and A.M. Frieze, On the complexity of partitioning graphs into connected subgraphs, Discrete Appl. Math. 10 (1985) 139–153.
  13. J. Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965) 449–467.
  14. R. Faudree, E. Flandrin and Z. Ryjáček, Claw-free graphs–-A survey, Discrete Math. 164 (1997) 87–147.
  15. H. Fleischner, In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts, Monatsh. Math. 82 (1976) 125–149.
  16. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman Co., New York, 1990).
  17. E. Győri, On division of graphs to connected subgraphs, in : Combinatorics Proc. 5th Hungarian Colloq. (1976) 485–494.
  18. M. Horňák, A. Marczyk, I. Schiermeyer and M. Woźniak, Dense arbitrarily vertex decomposable graphs, Graphs Combin. 28 (2012) 807–821.
  19. M. Horňák, Zs. Tuza and M. Woźniak, On-line arbitrarily vertex decomposable trees, Discrete Appl. Math. 155 (2007) 1420–1429.
  20. R. Kalinowski, M. Pilśniak, I. Schiermeyer and M. Woźniak, Dense arbitrarily partitionable graphs, Discuss. Math. Graph Theory 36 (2016) 5–22.
  21. L. Lovász, A homology theory for spanning trees of a graph, Acta Math. Acad. Sci. Hungar. 30 (1977) 241–251.
  22. A. Marczyk, An Ore-type condition for arbitrarily vertex decomposable graphs, Discrete Math. 309 (2009) 3588–3594.
  23. O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55.
  24. R. Ravaux, Graphes arbitrairement partitionnables: propriétés structurelles et algorithmiques, Ph.D. Thesis (Université de Versailles Saint-Quentin, France, 2009).