zbMATH — the first resource for mathematics

Covering all cliques of a graph. (English) Zbl 0744.05040
Summary: The following conjecture of T. Gallai is proved: If \(G\) is a chordal graph on \(n\) vertices, such that all its maximal complete subgraphs have order at least 3, then there is a vertex set of cardinality \(\leq n/3\) which meets all maximal complete subgraphs of \(G\). Further related results are given.

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
PDF BibTeX Cite
Full Text: DOI
[1] Aigner, M.; Andreae, T., Vertex-sets that meet all maximal cliques of a graph, (1986), manuscript
[2] Andreae, T., Covering the maximal cliques of a graph with at most half of its vertices, (1987), manuscript
[3] Berge, C., Graphs and hypergraphs, (1973), North-Holland Amsterdam · Zbl 0483.05029
[4] Dirac, G.A., On rigid circuit graphs, Abh. math. sem. univ. Hamburg, 25, 71-76, (1961) · Zbl 0098.14703
[5] P. Erdős, T. Gallai and Zs. Tuza, Covering the cliques of a graph with vertices, Discrete Math., to appear.
[6] Farber, M., Characterizations of strongly chordal graphs, Discrete math., 43, 173-189, (1983) · Zbl 0514.05048
[7] Gallai, T., Über extreme punkt- und kantenmengen, Ann. univ. sci. L. Eötvös sect. math., 2, 133-138, (1959) · Zbl 0094.36105
[8] Tuza, Zs., Extremal problems on graphs and hypergraphs, () · Zbl 0584.05042
[9] Zs. Tuza, Matchings and coverings in regular uniform hypergraphs, to appear. · Zbl 0541.05046
[10] Alon, N., Transversal numbers of uniform hypergraphs, Graphs and combinatorics, 6, 1-4, (1990) · Zbl 0742.05065
[11] T. Andreae, M. Schughart, and Zs. Tuza, Clique-transversal sets of line graphs and complements of line graphs, Discrete Math., to appear. · Zbl 0734.05077
[12] Feng-Chu Lai and G.J. Chang, An upper bound for the transversal numbers of 4-uniform hypergraphs, J. Combin. Theory Ser. B, to appear. · Zbl 0739.05068
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.