A New Characterization of P-k-Free Graphs

作者：Camby Eglantine; Schaudt Oliver^*

来源：Algorithmica, 2016, 75(1): 205-217.

DOI：10.1007/s00453-015-9989-6

• P-k-free graph
• Connected domination
• Computational complexity

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.

• 出版日期2016-5