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/