DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

F.X. Liu

Fengxia Liu

College of Mathematics and System Sciences, Xinjiang University
Urumqi, Xinjiang, 830046, P.R.China

email: xjulfx@163.com

B. Wu

Baoyindureng Wu

College of Mathematics and System Sciences, Xinjiang University
Urumqi, Xinjiang, 830046, P.R.China

email: baoywu@163.com

0000-0001-7164-3116

J.X. Meng

Jixiang Meng

College of Mathematics and System Sciences, Xinjiang University
Urumqi, Xinjiang, 830046, P.R.China

email: mjx@xju.edu.cn

Title:

Arbitrarily partitionable $\{2K_2, C_4\}$-free graphs

PDF

Source:

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:

  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 $C_4$ and $2K_2$, 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 $2K_2$-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

Close