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: |
|
||||||||||||
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: |
|
||||||||||||
Refereed: | Yes | ||||||||||||
URI: | http://kups.ub.uni-koeln.de/id/eprint/27715 |
Downloads
Downloads per month over past year
Altmetric
Export
Actions (login required)
View Item |