Back to Search
Start Over
Optimal-size clique transversals in chordal graphs
- Publication Year :
- 2016
-
Abstract
- The following question was raised by Tuza in 1990 and Erdos et al. in 1992: if every edge of an n-vertex chordal graph G is contained in a clique of size at least four, does G have a clique transversal, i.e., a set of vertices meeting all non-trivial maximal cliques, of size at most n/4? We prove that every such graph G has a clique transversal of size at most 2(n-1)/7 if n>=5, which is the best possible bound.
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1601.05305
- Document Type :
- Working Paper