# 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.

##### MSC:
 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)
##### Keywords:
covering; cliques; linear time algorithm; triangle-free graph
Full Text:
##### References:
  Aigner, M.; Andreae, T., Vertex-sets that meet all maximal cliques of a graph, (1986), manuscript  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  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  Brooks, R.L., On colouring the nodes of a network, Proc. Cambridge philos. soc., 37, 194-197, (1941) · Zbl 0027.26403  Caro, Y.; Tuza, Zs., Improved lower bounds on k-independence, J. graph theory, 15, 99-107, (1991) · Zbl 0753.68079  Erdős, P., Graph theory and probability II, Canad. J. math., 13, 346-352, (1961) · Zbl 0097.39102  Erdős, P.; Szekeres, G., A combinatorial problem in geometry, Compositio math., 2, 463-470, (1935) · JFM 61.0651.04  Lonc, Z.; Rival, I., Chains, antichains and fibres, J. combin. theory ser. A, 44, 207-228, (1987) · Zbl 0637.06001  Poljak, S., A note on stable sets and colourings of graphs, Comment. math. univ. carolin., 15, 307-309, (1974) · Zbl 0284.05105  Sands, B., Private communication, (July 1989)  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.