The clique-transversal set problem in {claw,K4}-free planar graphs

A clique is defined as a complete subgraph maximal under inclusion and having at least two vertices. A clique-transversal set D of a graph G=(V,E) is a subset of vertices of G such that D meets all cliques of G. The clique-transversal set problem is to find a minimum clique-transversal set of G. The...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2017-02, Vol.118, p.64-68
Main Authors: Liang, Zuosong, Shan, Erfang, Kang, Liying
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial problems
Graph algorithms
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A clique is defined as a complete subgraph maximal under inclusion and having at least two vertices. A clique-transversal set D of a graph G=(V,E) is a subset of vertices of G such that D meets all cliques of G. The clique-transversal set problem is to find a minimum clique-transversal set of G. The clique-transversal set problem has been proved to be NP-complete in planar graphs. This paper gives a polynomial-time algorithm for the clique-transversal set problem in {claw,K4}-free planar graphs. •Clique-transversal set problem is to find a minimum clique-transversal set of graphs.•Clique-transversal set problem (CTS) is proved to be NP-complete in planar graphs.•We give a polynomial algorithm for the CTS problem in {claw,K4}-free planar graphs.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2016.10.001