Covering the cliques of a graph with vertices (Q1201260): Difference between revisions

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.