A New Characterization of Pk -Free Graphs

Let $G$ be a connected $P_k$ ‐free graph, $k\ge 4$ . We show that $G$ admits a connected dominating set that induces either a $P_{k‐2}$ ‐free graph or a graph isomorphic to $P_{k‐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 $P_{k‐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 $P_{k‐2}$ ‐free or isomorphic to $P_{k‐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.