Covering the cliques of a graph with vertices (Q1201260)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Covering the cliques of a graph with vertices
scientific article

    Statements

    Covering the cliques of a graph with vertices (English)
    0 references
    0 references
    0 references
    0 references
    17 January 1993
    0 references
    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.
    0 references
    covering
    0 references
    cliques
    0 references
    linear time algorithm
    0 references
    triangle-free graph
    0 references

    Identifiers