A New Characterization of P_k-free Graphs

DOI10.1007/978-3-319-12340-0_11MaRDI QIDQ2945184zbMATH OpenOpenAlexFDO

Authors Eglantine Camby, Oliver Schaudt

Publication date 9 September 2015

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.7213

zbMATH Keywords

\(P_k\)-free graphcomputational complexityconnected domination

Mathematics Subject Classification ID

Paths and cycles (05C38) Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

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, $kge4$. 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]. 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 $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-Colorability, an NP-complete problem in general, can be solved in polynomial time for hypergraphs whose vertex-hyperedge incidence graph is $P_7$-free.

Recommendations

• A new characterization of P_k-free graphs
• A New Characterization of P 6-Free Graphs
• A new characterization of \(P_{6}\)-free graphs
• Knocking out \(P _{k }\)-free graphs
• A new characterization of unichord-free graphs
• Characterization of \(P_{6}\)-free graphs
• Knocking out \(P_k\)-free graphs
• The structure of \(TK_ a\)-free graphs
• Characterizations of \((4 K_1,C_4,C_5)\)-free graphs
• A new characterization of HH-free graphs

Cited in

(8)

• Perfect edge domination: hard and solvable cases
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Structural domination and coloring of some ( P₇ , C₇)-free graphs
• A new characterization of P_k-free graphs
• A New Characterization of P 6-Free Graphs
• Characterization of \(P_{6}\)-free graphs
• A new characterization of unichord-free graphs
• A new characterization of \(P_{6}\)-free graphs

This page was built for publication: A New Characterization of $$P_k$$-free Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945184)