×

zbMATH — the first resource for mathematics

On covering all cliques of a chordal graph. (English) Zbl 0846.05050
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}\).

MSC:
05C35 Extremal problems in graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andreae, T.; Schughart, M.; Tuza, Zs., Clique-transversal sets of line graphs and complements of line graphs, Discrete math., 88, 11-20, (1991) · Zbl 0734.05077
[2] Duffus, D.; Kierstead, H.A.; Trotter, W.T., Fibres and ordered set coloring, J. combin. theory ser. A, 58, 158-164, (1991) · Zbl 0757.06001
[3] Duffus, D.; Sands, B.; Sauer, N.; Woodrow, R.E., Two-coloring all two-element maximal antichains, J. combin. theory ser. A, 57, 109-116, (1991) · Zbl 0742.06004
[4] Erdős, P.; Gallai, T.; Tuza, Zs., Covering the cliques of a graph with vertices, Discrete math., 108, 279-289, (1992) · Zbl 0766.05063
[5] Flotow, C., Obere schranken fuer die clique-transversalzahl eines graphen, ()
[6] Lonc, Z.; Rival, I., Chains, antichains and fibres, J. combin. theory ser. A, 44, 207-228, (1987) · Zbl 0637.06001
[7] Maltby, R., A smallest-fibre-size to poset-size ratio approaching \(815\), J. combin. theory ser. A, 61, 328-330, (1992) · Zbl 0766.06006
[8] Tuza, Zs., Covering all cliques of a graph, Discrete math., 86, 117-126, (1990) · Zbl 0744.05040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.