Universität zu Köln

Bruhn, Henning, Joos, Felix and Schaudt, Oliver (2018). Long cycles through prescribed vertices have the Erdos-Posa property. J. Graph Theory, 87 (3). S. 275 - 285. HOBOKEN: WILEY. ISSN 1097-0118

Full text not available from this repository.

Abstract

We prove that for every graph, any vertex subset S, and given integers k,l: there are k disjoint cycles of length at least l that each contain at least one vertex from S, or a vertex set of size O(l . k log k) that meets all such cycles. This generalizes previous results of Fiorini and Herinckx and of Pontecorvi and Wollan. In addition, we describe an algorithm for our main result that runs in O(k log k . s(2) . (f (l) . n + m)) time, where s denotes the cardinality of S.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Bruhn, Henning UNSPECIFIED UNSPECIFIED UNSPECIFIED Joos, Felix UNSPECIFIED UNSPECIFIED UNSPECIFIED Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-194270
DOI:	10.1002/jgt.22156
Journal or Publication Title:	J. Graph Theory
Volume:	87
Number:	3
Page Range:	S. 275 - 285
Date:	2018
Publisher:	WILEY
Place of Publication:	HOBOKEN
ISSN:	1097-0118
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language PACKING DIRECTED CIRCUITS; HIGHLY CONNECTED GRAPHS; DISJOINT CYCLES; ODD CYCLES; MINORS Multiple languages Mathematics Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/19427