Geodesic
Arbitrarily Partitionable {2K2, C4}-Free Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 485-500.

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

A graph G = (V, E) of order n is said to be arbitrarily partitionable if for each sequence λ = (λ1, λ2, …, λp) of positive integers with λ1 + … +λp = n, there exists a partition (V1, V2, … , Vp) of the vertex set V such that Vi induces a connected subgraph of order λi in G for each i ∈ 1, 2, …, p. In this paper, we show that a threshold graph is arbitrarily partitionable if and only if it admits a perfect matching or a near perfect matching. We also give a necessary and sufficient condition for a 2K2, C4-free graph being arbitrarily partitionable, as an extension for a result of Broersma, Kratsch and Woeginger [Fully decomposable split graphs, European J. Combin. 34 (2013) 567–575] on split graphs.
Keywords: arbitrarily partitionable graphs, arbitrarily vertex decomposable, threshold graphs, {2 K 2, C 4 }-free graphs 
@article{DMGT_2022_42_2_a9,
     author = {Liu, Fengxia and Wu, Baoyindureng and Meng, Jixiang},
     title = {Arbitrarily {Partitionable} {{2K\protect\textsubscript{2},} {C\protect\textsubscript{4}}-Free} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {485--500},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a9/}
}
TY  - JOUR
AU  - Liu, Fengxia
AU  - Wu, Baoyindureng
AU  - Meng, Jixiang
TI  - Arbitrarily Partitionable {2K2, C4}-Free Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 485
EP  - 500
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a9/
LA  - en
ID  - DMGT_2022_42_2_a9
ER  - 
%0 Journal Article
%A Liu, Fengxia
%A Wu, Baoyindureng
%A Meng, Jixiang
%T Arbitrarily Partitionable {2K2, C4}-Free Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 485-500
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a9/
%G en
%F DMGT_2022_42_2_a9
Liu, Fengxia; Wu, Baoyindureng; Meng, Jixiang. Arbitrarily Partitionable {2K2, C4}-Free Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 485-500. http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a9/

[1] D. Barth, O. Baudon and J. Puech, Decomposable trees: a polynomial algorithm for tripodes, Discrete Math. 119 (2002) 205-216. https://doi.org/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. https://doi.org/10.1016/j.disc.2006.01.006

[3] D. Barth, H. Fournier and R. Ravaux, On the shape of decomposable trees, Discrete Math. 309 (2009) 3882–3887. https://doi.org/10.1016/j.disc.2008.11.012

[4] O. Baudon, J. Bensmail, F. Foucaud and M. Pilśniak, Structural properties of recursively partitionable graphs with connectivity 2, Discus. Math. Graph Theory 37 (2017) 89–115. https://doi.org/10.7151/dmgt.1925

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

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

[7] 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. https://doi.org/10.1016/j.dam.2013.09.007

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

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

[10] J. Bensmail, On the complexity of partitioning a graph into a few connected subgraphs, J. Comb. Optim. 30 (2015) 174–187. https://doi.org/10.1007/s10878-013-9642-8

[11] Z. Blázsik, M. Hujter, A. Pluhár and Zs. Tuza, Graphs with no induced C4 and 2K2, Discrete Math. 115 (1993) 51–55. https://doi.org/10.1016/0012-365X(93)90477-B

[12] H. Broersma, D. Kratsch and G.J. Woeginger, Fully decomposable split graphs, European J. Combin. 34 (2013) 567–575. https://doi.org/10.1016/j.ejc.2011.09.044

[13] F.R.K. Chung, A. Gyárfás, Zs. Tuza and W.T. Trotter, The maximum number of edges in 2K2-free graphs of bounded degree, Discrete Math. 81 (1990) 129–135. https://doi.org/10.1016/0012-365X(90)90144-7

[14] V. Chvátal and P.L. Hammer, Aggregation of inequalities in integer programming, Ann. Discrete Math. 1 (1977) 145–162. https://doi.org/10.1016/S0167-5060(08)70731-3

[15] S. Cichacz, A. Görlich, A. Marczyk and J. Przybyło, Arbitrarily vertex decomposable caterpillars with four or five leaves, Discuss. Math. Graph Theory 26 (2006) 291–305. https://doi.org/10.7151/dmgt.1321

[16] S. Földes, P.L. Hammer, Split graphs, Congr. Numer. XIX (1977) 311–315.

[17] E. Győri, On division of graphs to connected subgraphs, in: Combinatorics, Proc. Fifth Hungarian Colloq., (Keszthely, 1976, Colloq. Math. Soc. János Bolyai 18, 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. https://doi.org/10.1007/s00373-011-1077-3

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

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

[21] M. Horňák and M. Woźniak, On arbitrarily vertex decomposable trees, Discrete Math. 308 (2008) 1268–1281. https://doi.org/10.1016/j.disc.2007.04.008

[22] R. Kalinowski, Dense on-line arbitrarily partitionable graphs, Discrete Appl. Math. 226 (2017) 71–77. https://doi.org/10.1016/j.dam.2017.04.006

[23] R. Kalinowski, M. Pilśniak, I. Schiermeyer and M. Woźniak, Dense arbitrarily partitionable graphs, Discuss. Math. Graph Theory 36 (2016) 5–22. https://doi.org/10.7151/dmgt.1833

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

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

[26] L. Lovász, A homology theory for spanning trees of a graph, Acta Math. Acad. Sci. Hungar. 30(3-4) (1977) 241–251. https://doi.org/10.1007/BF01896190

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

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

[29] R. Ravaux, Decomposing trees with large diameter, Theoret. Comput. Sci. 411 (2010) 3068–3072. https://doi.org/10.1016/j.tcs.2010.04.032