Article in volume
Authors:
Title:
Arbitrarily partitionable $\{2K_2, C_4\}$-free graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(2) (2022) 485-500
Received: 2018-12-02 , Revised: 2019-11-30 , Accepted: 2019-11-30 , Available online: 2020-01-13 , https://doi.org/10.7151/dmgt.2289
Abstract:
A graph $G=(V,E)$ of order $n$ is said to be arbitrarily partitionable if for
each sequence $\lambda=(\lambda_1, \lambda_2, \dots, \lambda_p)$ of positive
integers with $\lambda_1+\cdots+\lambda_p=n$, there exists a partition
$(V_1, V_2, \dots, V_p)$ of the vertex set $V$ such that $V_i$ induces a
connected subgraph of order $\lambda_i$ in $G$ for each $i\in \{1,2,\dots,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 $\{2K_2, C_4\}$-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, $\{2K_2, C_4\}$-free graphs
References:
- 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 - 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 - 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 - 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 - 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.
- 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 - 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 - 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 - 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 - 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 - Z. Blázsik, M. Hujter, A. Pluhár and Zs. Tuza, Graphs with no induced $C_4$ and $2K_2$, Discrete Math. 115 (1993) 51–55.
https://doi.org/10.1016/0012-365X(93)90477-B - 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 - F.R.K. Chung, A. Gyárfás, Zs. Tuza and W.T. Trotter, The maximum number of edges in $2K_2$-free graphs of bounded degree, Discrete Math. 81 (1990) 129–135.
https://doi.org/10.1016/0012-365X(90)90144-7 - 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 - 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 - S. Földes, P.L. Hammer, Split graphs, Congr. Numer. XIX (1977) 311–315.
- 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.
- 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 - 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 - M. Horňák and M. Woźniak, Arbitrarily vertex decomposable trees are of maximum degree at most six, Opuscula Math. 23 (2003) 49–62.
- 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 - 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 - 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 - 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 - 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 - 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 - A. Marczyk, A note on arbitrarily vertex decomposable graphs, Opuscula Math. 26 (2006) 109–118.
- 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 - R. Ravaux, Decomposing trees with large diameter, Theoret. Comput. Sci. 411 (2010) 3068–3072.
https://doi.org/10.1016/j.tcs.2010.04.032
Close