Advertisement
Published in:
2014 | OriginalPaper | Chapter
A New Characterization of \(P_k\)-free Graphs
Authors : Eglantine Camby, Oliver Schaudt
Published in: Graph-Theoretic Concepts in Computer Science
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
The class of graphs that do not contain an induced path on \(k\) vertices, \(P_k\)-free graphs, plays a prominent role in algorithmic graph theory. This motivates the search for special structural properties of \(P_k\)-free graphs, including alternative characterizations.
Let \(G\) be a connected \(P_k\)-free graph, \(k \ge 4\). We show that \(G\) admits a connected dominating set whose induced subgraph is either \(P_{k-2}\)-free, or isomorphic to \(P_{k-2}\). Surprisingly, it turns out that 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 whose induced subgraph is either \(P_{k-2}\)-free, or isomorphic to \(C_k\). This improves and generalizes several previous results; the particular case of \(k=7\) solves a problem posed by van ’t Hof and Paulusma [A new characterization of \(P_6\)-free graphs, COCOON 2008] [12].
In the second part of the paper, 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 \(P_{k-2}\)-free or isomorphic to \(P_{k-2}\).
As an application our results, we prove that Hypergraph 2-Colora
bility, an NP-complete problem in general, can be solved in polynomial time for hypergraphs whose vertex-hyperedge incidence graph is \(P_7\)-free.