zbMATH — the first resource for mathematics

Covering the cliques of a graph with vertices. (English) Zbl 0766.05063
Here all graphs have order \(n\) and isolated vertics are not counted as cliques. The central problem studied is that of estimating the cardinality \(\tau_c(G)\) of the smallest set that shares a vertex with each clique of \(G\). Among other results it is shown that \(\tau_c(G)\leq n-\sqrt{2n}+{3\over 2}\) and a linear time (in the number of edges) algorithm for achieving this bound is proposed. Four associated problems are presented. For example, it is asked if \(\tau_c(G)\leq n-r(n)\) for all graphs \(G\) where \(r(n)\) is the largest integer such that every triangle-free graph contains an independent set of \(r(n)\) vertices. Also, how large triangle-free induced subgraphs does a \(K_4\)-free graph \(G\) contain.

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI
[1] Aigner, M.; Andreae, T., Vertex-sets that meet all maximal cliques of a graph, (1986), manuscript
[2] Ajtai, M.; Komlós, J.; Szemerédi, E., A note on Ramsey numbers, J. combin. theory ser. A, 29, 354-360, (1980) · Zbl 0455.05045
[3] Andreae, T.; Schughart, M.; Tuza, Zs., Clique-tranversal sets of line graphs and complements of line graphs, Discrete math., 88, 11-20, (1991) · Zbl 0734.05077
[4] Brooks, R.L., On colouring the nodes of a network, Proc. Cambridge philos. soc., 37, 194-197, (1941) · Zbl 0027.26403
[5] Caro, Y.; Tuza, Zs., Improved lower bounds on k-independence, J. graph theory, 15, 99-107, (1991) · Zbl 0753.68079
[6] Erdős, P., Graph theory and probability II, Canad. J. math., 13, 346-352, (1961) · Zbl 0097.39102
[7] Erdős, P.; Szekeres, G., A combinatorial problem in geometry, Compositio math., 2, 463-470, (1935) · JFM 61.0651.04
[8] Lonc, Z.; Rival, I., Chains, antichains and fibres, J. combin. theory ser. A, 44, 207-228, (1987) · Zbl 0637.06001
[9] Poljak, S., A note on stable sets and colourings of graphs, Comment. math. univ. carolin., 15, 307-309, (1974) · Zbl 0284.05105
[10] Sands, B., Private communication, (July 1989)
[11] 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.