| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4649961 | Discrete Mathematics | 2008 | 7 Pages |
A P4P4-transversal of a graph GG is a set of vertices TT which meet every P4P4 of GG. A P4P4-transversal TT is called stable if there are no edges in the subgraph of GG induced by TT. It has been previously shown by Hoàng and Le that it is NP-complete to decide whether a comparability (and hence perfect) graph GG has a stable P4P4-transversal. In the following we show that the problem is NP-complete for chordal graphs. We apply this result to show that two related problems of deciding whether a chordal graph has a P3P3-free P4P4-transversal, and deciding whether a chordal graph has a P4P4-free P4P4-transversal (also known as a two-sided P4P4-transversal) are both NP-complete. Additionally, we strengthen the main results to strongly chordal graphs.
