Paper Info
Title
On the clique-transversal number of chordal graphs
Abstract
For a graph G , a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and | bC | ⩾ 2. The clique-transversal number τ c ( G ) is the minimum cardinality of a set of vertices which meets all cliques of G . For k ⩾ 4, let G k be the class of chordal graphs for which all cliques are either k -cliques (i.e., cliques of order k ) or triangles and for which each edge is contained in at least one k -cliques. In response to a question of Tuza, it was shown by Andreae and Flotow (1996) that (i) τ c (G) |G| < 2 7 for all members of a certain subclass G 4 ∗ of G 4 and (ii) this bound is best possible, i.e., sup { τ c (G) |G| : G ∈ G 4 ∗} = 2 7 . In the present paper, a theorem is presented which extends and generalizes this result. It is shown that τ c (G) |G| < min 2 (k + 3) , 3 (2k + 1) for all G ∈ G k (k ⩾ 4) and a lower bound for σ k = sup τ c (G) |G| : G ∈ G k is established. In particular, these results show that (σ k 2k) 3 → 1 for k → ∞.
Year
DOI
Venue
1998
10.1016/S0012-365X(98)00087-9
Discrete Mathematics
Keywords
Field
DocType
perfect graphs,clique-transversal number,chordal graphs,chordal graph,lower bound,perfect graph
Discrete mathematics,Combinatorics,Clique,Vertex (geometry),K-tree,Upper and lower bounds,Chordal graph,Clique-sum,Cardinality,Transversal (geometry),Mathematics
Journal
Volume
Issue
ISSN
191
1-3
Discrete Mathematics
Citations 
PageRank 
References 
17
1.04
8
Authors
1
Name
Order
Citations
PageRank
Thomas Andreae1171.04