Universität zu Köln

Camby, Eglantine ORCID: 0000-0002-7290-9286 and Schaudt, Oliver (2016). A New Characterization of P-k-Free Graphs. Algorithmica, 75 (1). S. 205 - 218. NEW YORK: SPRINGER. ISSN 1432-0541

Full text not available from this repository.

Abstract

Let G be a connected P-k-free graph, k >= 4. We show that G admits a connected dominating set that induces either a Pk-2-free graph or a graph isomorphic to Pk-2. In fact, every minimum connected dominating set of G has this property. This yields a new characterization for P-k-free graphs: a graph G is P-k-free if and only if each connected induced subgraph of G has a connected dominating set that induces either a Pk-2-free graph, or a graph isomorphic to C-k. We present an efficient algorithm that, given a connected graph G, computes a connected dominating set X of G with the following property: for the minimum k such that G is P-k - free, the subgraph induced by X is Pk-2-free or isomorphic to Pk-2. As an application our results, we prove that Hypergraph 2-Colorability can be solved in polynomial time for hypergraphs whose vertex-hyperedge incidence graphs is P-7-free.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Camby, Eglantine UNSPECIFIED orcid.org/0000-0002-7290-9286 UNSPECIFIED Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-277158
DOI:	10.1007/s00453-015-9989-6
Journal or Publication Title:	Algorithmica
Volume:	75
Number:	1
Page Range:	S. 205 - 218
Date:	2016
Publisher:	SPRINGER
Place of Publication:	NEW YORK
ISSN:	1432-0541
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language Computer Science, Software Engineering; Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/27715