On image-transversals of chordal graphs Original Research Article

A image-transversal of a graph image is a set of vertices image which meet every image of image. A image-transversal image is called stable if there are no edges in the subgraph of image induced by image. It has been previously shown by Hoàng and Le that it is image-complete to decide whether a comparability (and hence perfect) graph image has a stable image-transversal. In the following we show that the problem is image-complete for chordal graphs. We apply this result to show that two related problems of deciding whether a chordal graph has a image-free image-transversal, and deciding whether a chordal graph has a image-free image-transversal (also known as a two-sided image-transversal) are both image-complete. Additionally, we strengthen the main results to strongly chordal graphs.