Hell, Pavol; Kirkpatrick, David; Kratochvíl, Jan; Kříž, Igor On restricted two-factors. (English) Zbl 0672.05065 SIAM J. Discrete Math. 1, No. 4, 472-484 (1988). Summary: A two-factor of G consists of disjoint cycles that cover V(G). The authors consider the existence problem for two-factors in which the cycles are restricted to having lengths from a prescribed (possibly infinite) set of integers. Theorems are presented which derive the existence of such restricted two-factors in G from their existence in G-u and G-v. The possibility of such theorems is then related to the complexity of the corresponding existence problem. In particular, the only four cases in which polynomial algorithms can be expected (in the sense that all other cases are shown to be NP-hard) are identified. Cited in 19 Documents MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C38 Paths and cycles 05C99 Graph theory Keywords:triangle-free; two-factor; disjoint cycles; polynomial algorithms PDFBibTeX XMLCite \textit{P. Hell} et al., SIAM J. Discrete Math. 1, No. 4, 472--484 (1988; Zbl 0672.05065) Full Text: DOI