2014/02/28 by Eglantine Camby, Oliver Schaudt, Camby, Eglantine +1
Computer Science · Engineering · Mathematics · #05C38 #05C69 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #cs.DM #graph theory and CDMA systems #math.CO #msc:05C38 #msc:05C69 #msc:05C75
paper · pdf · doi:10.48550/arxiv.1402.7213
13 pages, 4 figures
arxiv created 2014/02/28 · openalex publication_date 2014/02/28 · arxiv updated 2014/03/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The class of graphs that do not contain an induced path on k vertices, Pk-free graphs, plays a prominent role in algorithmic graph theory. This motivates the search for special structural properties of Pk-free graphs, including alternative characterizations. Let G be a connected Pk-free graph, k ≥ 4. We show that G admits a connected dominating set whose induced subgraph is either Pk-2-free, or isomorphic to Pk-2. Surprisingly, it turns out that every minimum connected dominating set of G has this property. This yields a new characterization for Pk-free graphs: a graph G is Pk-free if and only if each connected induced subgraph of G has a connected dominating set whose induced subgraph is either Pk-2-free, or isomorphic to Ck. 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 P6-free graphs, COCOON 2008]. In the second part of the paper, we present an efficient algorithm that, given a connected graph G on n vertices and m edges, computes a connected dominating set X of G with the following property: for the minimum k such that G is Pk-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, an NP-complete problem in general, can be solved in polynomial time for hypergraphs whose vertex-hyperedge incidence graph is P7-free.