Covering the cliques of a graph with vertices
type: Item
instance of: scholarly article
title: Covering the cliques of a graph with vertices
zbMATH Open document ID: 0766.05063
DOI: 10.1016/0012-365X(92)90681-5
author: Zsolt Tuza
author: P. Erdős
author: Tibor Gallai
published in: Discrete Mathematics
publication date: 1993-01-17T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 97508
zbMATH Keywords: covering
zbMATH Keywords: cliques
zbMATH Keywords: linear time algorithm
zbMATH Keywords: triangle-free graph
Wikidata QID: Q105471961
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: A note on Ramsey numbers
cites work: Clique-transversal sets of line graphs and complements of line graphs
cites work: Q5782525
cites work: Improved lower bounds on k‐independence
cites work: Graph Theory and Probability. II
cites work: Chains, antichains, and fibres
cites work: Q4770411
cites work: Covering all cliques of a graph
full work available at URL: 0012-365x(92)90681-5
OpenAlex ID: W2086357278
description: scientific article; zbMATH DE number 97508