On the complexity of some edge-partition problems for graphs

被引：7
|
作者：
Lonc, Z
机构：
[1] Institute of Mathematics, Warsaw University of Technology
来源：
DISCRETE APPLIED MATHEMATICS | 1996年 / 70卷 / 02期
关键词：
D O I：
10.1016/0166-218X(95)00107-3
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
For a family g of stars, a g-decomposition of a graph H is a partition of the edge set of H into subgraphs isomorphic to members of V. We show that, if g contains neither the 1-edge nor the 2-edge star, it is NP-complete to decide whether a bipartite graph admits a g-decomposition. This result enables us to strengthen a result of Hell and Kirkpatrick on partitioning the vertex set of a graph into complete graphs of certain orders. If g contains a 2-edge star, we obtain a good characterization of graphs (not necessarily bipartite) that admit g-decompositions. This characterization yields a linear time algorithm for constructing such a decomposition, if it exists.
引用
收藏
页码：177 / 183
页数：7
相关论文
共 50 条
  • [31] Edge clique partition in (k, l)-graphs
    Jones, Atila A.
    Protti, Fabio
    Del-Vecchio, Renata R.
    DISCRETE APPLIED MATHEMATICS, 2022, 306 : 89 - 97
  • [32] COMPLEXITY OF DIMENSION 3 AND SOME RELATED EDGE-COVERING CHARACTERISTICS OF GRAPHS
    KUCERA, L
    NESETRIL, J
    PULTR, A
    THEORETICAL COMPUTER SCIENCE, 1980, 11 (01) : 93 - 106
  • [33] Complexity and approximation of Satisfactory Partition problems
    Bazgan, C
    Tuza, Z
    Vanderpooten, D
    COMPUTING AND COMBINATORICS, PROCEEDINGS, 2005, 3595 : 829 - 838
  • [34] On the complexity of graph tree partition problems
    Cordone, R
    Maffioli, F
    DISCRETE APPLIED MATHEMATICS, 2004, 134 (1-3) : 51 - 65
  • [35] A linear-time algorithm for finding an edge-partition with max-min ratio at most two
    Chu, An-Chiang
    Wu, Bang Ye
    Chao, Kun-Mao
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (7-8) : 932 - 943
  • [36] Equitable partition for some Ramanujan graphs
    Alinejad, M.
    Erfanian, A.
    Fulad, S.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2023, 15 (05)
  • [37] Extension of some edge graph problems: Standard, parameterized and approximation complexity
    Casel, Katrin
    Fernau, Henning
    Ghadikolaei, Mehdi Khosravian
    Monnot, Jerome
    Sikora, Florian
    DISCRETE APPLIED MATHEMATICS, 2023, 340 : 183 - 201
  • [38] A note on the complexity of the total domatic partition problem in graphs
    Lee, Chuan-Min
    Wu, Sz-Lin
    Chen, Hsin-Lun
    Chang, Chia-Wei
    Lee, Tai
    Journal of Combinatorial Mathematics and Combinatorial Computing, 2019, 108 : 3 - 14
  • [39] A characterization of edge-perfect graphs and the complexity of recognizing some combinatorial optimization games
    Dobson, M. P.
    Leoni, V.
    Nasini, G.
    DISCRETE OPTIMIZATION, 2013, 10 (01) : 54 - 60
  • [40] The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
    van Bevern, Rene
    Fluschnik, Till
    Mertzios, George B.
    Molter, Hendrik
    Sorge, Manuel
    Suchy, Ondrej
    DISCRETE OPTIMIZATION, 2018, 30 : 20 - 50
12345