Abstract
We study -free graphs, i.e., graphs that do not contain an induced path on six vertices. Our main result is a new characterization of this graph class: a graph is -free if and only if each connected induced subgraph of on more than one vertex contains a dominating induced cycle on six vertices or a dominating (not necessarily induced) complete bipartite subgraph. This characterization is minimal in the sense that there exists an infinite family of -free graphs for which a smallest connected dominating subgraph is a (not induced) complete bipartite graph. Our characterization of -free graphs strengthens results of Liu and Zhou, and of Liu, Peng and Zhao. Our proof has the extra advantage of being constructive: we present an algorithm that finds such a dominating subgraph of a connected -free graph in polynomial time. This enables us to solve the Hypergraph 2-Colorability problem in polynomial time for the class of hypergraphs with -free incidence graphs.
| Original language | English |
|---|---|
| Pages (from-to) | 731-740 |
| Number of pages | 10 |
| Journal | Discrete applied mathematics |
| Volume | 158 |
| Issue number | 7 |
| DOIs | |
| Publication status | Published - 2010 |
| Externally published | Yes |