Abstract
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 P H the problem of exsitence of an H-decomposition of a graph. The Holyer's problem is to classify the problems PH according to their computational complexities. In this paper we outline the proof of polynomiality of the problem PH for H being the union of s disjoint 2-edge paths. This case is believed to bear the main difficulties among so far uncovered cases.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Alon: A note on the decomposition of graphs into isomorphic matchings, Acta Math. Acad. Sci. Hung. 42 (1983), 221–223
J.C. Bermond, D. Sotteau: Graph decomposition and G-designs, Proc. of the 5th British combinatorial conference, Aberdeen 1975
A. Bialostocki, Y. Roditty: 3K2-decomposition of a graph, Acta Math. Acad. Sci. Hung. 40 (1982), 201–208
J. Bosak: Graph Decompositions, Springer-Verlag 1990
A.E. Brouwer, R.M. Wilson: The decomposition of graphs into ladder graphs, Stiching Mathematisch Centrum (zn 97/80), Amsterdam 1980
F.R.K. Chung, R.L. Graham: Recent results in graph decompositions, In Combinatorics (H.N.V. Temperley, ed.), London Math. Soc., Lecture Notes Series 52 (1981), 103–124
E. Cohen, M. Tarsi: NP-completeness of graph decomposition problem, Journal of Complexity 7 (1991), 200–212
D. Dor, M. Tarsi: Graph decomposition is NPC — A complete proof of Holyer's conjecture, 1992, preprint
O. Favaron, Z. Lonc, M. Truszczyński: Decomposition of graphs into graphs with three edges, Ars Combinatoria 20 (1985), 125–146
P. Hell, D.G. Kirkpatrick: On the complexity of general graph factor problems, SIAM Journal of Computing 12(1983), 601–609
I. Holyer: The NP-completeness of some edge partition problems, SIAM J. of Comp. 10 (1981), 713–717
Masuyama, Hakimi: Edge packing in graphs, preprint
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lonc, Z. (1994). Towards a solution of the Holyer's problem. In: van Leeuwen, J. (eds) Graph-Theoretic Concepts in Computer Science. WG 1993. Lecture Notes in Computer Science, vol 790. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57899-4_48
Download citation
DOI: https://doi.org/10.1007/3-540-57899-4_48
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57899-4
Online ISBN: 978-3-540-48385-4
eBook Packages: Springer Book Archive