On the clique-transversal number in (claw, K 4)-free 4-regular graphs

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted by . C (G), is the minimum cardinality of a clique-transversal set in G. In this paper, we first present a lower bound on . C (G) and characterize the extremal graphs achieving the lower bound for a connected (claw, K 4)-free 4-regular graph G. Furthermore, we show that for any 2-connected (claw, K 4)-free 4-regular graph G of order n, its clique-transversal number equals to .n/3..