Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial. (English) Zbl 0868.05041
Let \(H\) be a fixed graph. We say that a graph \(G\) admits an \(H\)-decomposition if the set of edges of \(G\) can be partitioned into subsets generating graphs isomorphic to \(H\). Denote by \({\mathcal P}_H\) the problem of existence of an \(H\)-decomposition of a graph. The Holyer problem is to classify the problems \({\mathcal P}_H\) according to their computational complexities. In this paper we show that the problem \({\mathcal P}_H\) is polynomial when \(H\) is the union of \(s\) disjoint 2-edge paths.
Reviewer: Z.Lonc (Warszawa)
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Alon, N., A note on the decomposition of graphs into isomorphic matchings, Acta Math. Acad. Sci. Hung., 42, 221-223 (1983) · Zbl 0535.05047 |
| [2] | Bermond, J. C.; Sotteau, D., Graph decomposition and \(G\), Proceedings of the 5th British Combinatorial Conference (1975), Aberdeen · Zbl 0331.05021 |
| [3] | Bialostocki, A.; Roditty, Y., \(3K_2\), Acta Math. Acad. Sci. Hung., 40, 201-208 (1982) · Zbl 0467.05057 |
| [4] | Bosak, J., Graph Decompositions (1990), Kluwer Academic · Zbl 0726.05001 |
| [5] | A. E. Brouwer, R. M. Wilson, 1980, The decomposition of graphs into ladder graphs, Stiching Mathematisch Centrum (zn 97/80), Amsterdam; A. E. Brouwer, R. M. Wilson, 1980, The decomposition of graphs into ladder graphs, Stiching Mathematisch Centrum (zn 97/80), Amsterdam |
| [6] | Chung, F. R.K.; Graham, R. L., Recent results in graph decompositions, Combinatorics. Combinatorics, Lecture Notes Series, Vol. 52 (1981), Cambridge Univ. PressLondon Mathematical Society: Cambridge Univ. PressLondon Mathematical Society Cambridge · Zbl 0464.05046 |
| [7] | Cohen, E.; Tarsi, M., NP-completeness of graph decomposition problem, J. Complexity, 7, 200-212 (1991) · Zbl 0741.68055 |
| [8] | Corneil, D. G.; Masuyama, S.; Hakimi, S. L., Edge-disjoint packings of graphs, Discrete Appl. Math., 50, 135-148 (1994) · Zbl 0793.68114 |
| [9] | D. Dor, M. Tarsi, 1992, Graph decomposition is NPC—A complete proof of Holyer’s conjecture, Proceedings of the 24th Annual ACM Symposium on Theory of Computing; D. Dor, M. Tarsi, 1992, Graph decomposition is NPC—A complete proof of Holyer’s conjecture, Proceedings of the 24th Annual ACM Symposium on Theory of Computing · Zbl 0884.05071 |
| [10] | Favaron, O.; Lonc, Z.; Truszczyński, M., Decomposition of graphs into graphs with three edges, Ars Combinatoria, 20, 125-146 (1985) · Zbl 0604.05028 |
| [11] | Hell, P.; Kirkpatrick, D. G., On the complexity of general graph factor problems, SIAM J. Comput., 12, 601-609 (1983) · Zbl 0525.68023 |
| [12] | Holyer, I., The NP-completeness of some edge partition problems, SIAM J. Comput., 10, 713-717 (1981) · Zbl 0468.68069 |
| [13] | Priesler, M.; Tarsi, M., On the decomposition of the graphs into copies of \(P_3 tK_2\), Ars Combinatoria, 35, 325-333 (1993) · Zbl 0779.05036 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
