The Library
On P4-transversals of chordal graphs
Tools
Stacho, Juraj (2008) On P4-transversals of chordal graphs. Discrete Mathematics, Vol.308 (No.23). pp. 5548-5554. doi:10.1016/j.disc.2007.10.022 ISSN 0012-365X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.disc.2007.10.022
Abstract
A P4-transversal of a graph G is a set of vertices T which meet every P4 of G. A P4-transversal T is called stable if there are no edges in the subgraph of G induced by T. It has been previously shown by Hoàng and Le that it is -complete to decide whether a comparability (and hence perfect) graph G has a stable P4-transversal. In the following we show that the problem is -complete for chordal graphs. We apply this result to show that two related problems of deciding whether a chordal graph has a P3-free P4-transversal, and deciding whether a chordal graph has a P4-free P4-transversal (also known as a two-sidedP4-transversal) are both -complete. Additionally, we strengthen the main results to strongly chordal graphs.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Discrete Mathematics | ||||
Publisher: | Elsevier BV | ||||
ISSN: | 0012-365X | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | Vol.308 | ||||
Number: | No.23 | ||||
Page Range: | pp. 5548-5554 | ||||
DOI: | 10.1016/j.disc.2007.10.022 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |