On covering all cliques of a chordal graph
Let \(G\) be a graph without isolated vertices. A set \(T\subseteq V(G)\) is called a clique-transversal set if \(T\) has non-empty intersection with every maximal clique in \(G\). The clique-transversal number \(\tau_c(G)\) is the minimum cardinality of a clique-transversal set. Let \(\mathcal G\) denote the class of chordal graphs with the property that each edge is contained in a clique of order at least 4. The authors show that for each \(\varepsilon> 0\), there exists a graph \(G\in {\mathcal G}\) such that \(\tau_c(G)\geq ({2\over 7}- \varepsilon)\). They give some evidence to support their conjecture that \(\tau_c(G)\leq {2\over 7} |V(G)|\) for all \(G\in {\mathcal G}\).
scientific article; zbMATH DE number 858120