Geodesic
Dense Arbitrarily Partitionable Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 5-22.

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

A graph G of order n is called arbitrarily partitionable (AP for short) if, for every sequence (n_1, . . ., n_k) of positive integers with n_1 + ⋯ + n_k = n, there exists a partition (V_1, . . ., V_k) of the vertex set V(G) such that V_i induces a connected subgraph of order n_i for i = 1, . . ., k. In this paper we show that every connected graph G of order n ≥ 22 and with ‖G‖  gt; n-42 + 12 edges is AP or belongs to few classes of exceptional graphs.
Keywords: arbitrarily partitionable graph, Erdös-Gallai condition, traceable graph, perfect matching 
@article{DMGT_2016_36_1_a0,
     author = {Kalinowski, Rafa{\l} and Pil\'sniak, Monika and Schiermeyer, Ingo and Wo\'zniak, Mariusz},
     title = {Dense {Arbitrarily} {Partitionable} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {5--22},
     publisher = {mathdoc},
     volume = {36},
     number = {1},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a0/}
}
TY  - JOUR
AU  - Kalinowski, Rafał
AU  - Pilśniak, Monika
AU  - Schiermeyer, Ingo
AU  - Woźniak, Mariusz
TI  - Dense Arbitrarily Partitionable Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 5
EP  - 22
VL  - 36
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a0/
LA  - en
ID  - DMGT_2016_36_1_a0
ER  - 
%0 Journal Article
%A Kalinowski, Rafał
%A Pilśniak, Monika
%A Schiermeyer, Ingo
%A Woźniak, Mariusz
%T Dense Arbitrarily Partitionable Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 5-22
%V 36
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a0/
%G en
%F DMGT_2016_36_1_a0
Kalinowski, Rafał; Pilśniak, Monika; Schiermeyer, Ingo; Woźniak, Mariusz. Dense Arbitrarily Partitionable Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 5-22. http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a0/

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

[2] O. Baudon, J. Bensmail, R. Kalinowski, A. Marczyk, J. Przybyło and M. Woźniak, On the Cartesian product of an arbitrarily partitionable graph and a traceable graph, Discrete Math. Theor. Comput. Sci. 16 (2014) 225–232.

[3] O. Baudon, J. Bensmail, J. Przybyło and M. Woźniak, Partitioning powers of traceable or Hamiltonian graphs, Theoret. Comput. Sci. 520 (2014) 133–137. doi:10.1016/j.tcs.2013.10.016

[4] O. Baudon, F. Foucaud, J. Przybyło 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

[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] 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

[7] O. Baudon, J. Przybyło and M. Woźniak, On minimal arbitrarily partitionable graphs, Inform. Process. Lett. 112 (2012) 697–700. doi:10.1016/j.ipl.2012.06.010

[8] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).

[9] H.J. Broersma, D. Kratsch and G.J. Woeginger, Fully decomposable split graphs, Lecture Notes in Comput. Sci. 5874 (2009) 4105–4112. doi:10.1007/978-3-642-10217-2_13

[10] P. Erdős, Remarks on a paper of Pósa, Magyar Tud. Akad. Mat. Kutató Int. Kőzl. 7 (1962) 227–229.

[11] P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959) 337–356. doi:10.1007/BF02024498

[12] M. Horňák, A. Marczyk, I. Schiermeyer and M. Woźniak, Dense arbitrarily vertex decomposable graphs, Graphs Combin. 28 (2012) 807–821. doi:10.1007/s00373-011-1077-3

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

[14] 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

[15] R. Kalinowski, M. Pilśniak, M. Woźniak and I.A. Zioło, Arbitrarily vertex decomposable suns with few rays, Discrete Math. 309 (2009) 3726–3732. doi:10.1016/j.disc.2008.02.019

[16] R. Kalinowski, M. Pilśniak, M. Woźniak and I.A. Zioło, On-line arbitrarily vertex decomposable suns, Discrete Math. 309 (2009) 6328–6336. doi:10.1016/j.disc.2008.11.025

[17] A. Kemnitz and I. Schiermeyer, Improved degree conditions for Hamiltonian properties, Discrete Math. 312 (2012) 2140–2145. doi:10.1016/j.disc.2011.07.013

[18] A. Marczyk, A note on arbitrarily vertex decomposable graphs, Opuscula Math. 26 (2006) 109–118.

[19] 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

[20] D.R. Woodall, Maximal circuits of graphs I, Acta Math. Acad. Sci. Hungar. 28 (1976) 77–80. doi:10.1007/BF01902497