| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427821 | Information Processing Letters | 2011 | 4 Pages |
A clique-transversal set S of a graph G is a subset of vertices intersecting all the cliques of G, where a clique is a complete subgraph maximal under inclusion and having at least two vertices. A clique-independent set of the graph G is a set of pairwise disjoint cliques of G. The clique-transversal number τC(G)τC(G) of G is the cardinality of the smallest clique-transversal set in G and the clique-independence number αC(G)αC(G) of G is the cardinality of the largest clique-independent set in G . This paper proves that determining τC(G)τC(G) and αC(G)αC(G) is NP-complete for a cubic planar graph G of girth 3. Further we propose two approximation algorithms for determining τC(G)τC(G) and αC(G)αC(G) in a cubic graph G.
► The clique-transversal problem is NP-complete for cubic planar graphs. ► The clique-independent set problem is NP-complete for cubic planar graphs. ► We propose two approximation algorithms for the two problems.
