On the triangle clique cover and K_t clique cover problems

DOI10.1016/J.DISC.2019.111627zbMATH1429.05160OpenAlexW2752765779MaRDI QIDQ2279271FDOQ2279271

Authors Hoang Dau, Olgica Milenkovic, Gregory J. Puleo

Publication date 12 December 2019

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.01590

zbMATH Keywords

graph clusteringcommunity detectionintersection numberedge clique coverTuran graphtriangle clique cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: An edge clique cover of a graph is a set of cliques that covers all edges of the graph. We generalize this concept to "$K_t$ clique cover", i.e. a set of cliques that covers all complete subgraphs on $t$ vertices of the graph, for every $tgeq1$. In particular, we extend a classical result of Erd"os, Goodman, and P'osa (1966) on the edge clique cover number ($t=2$), also known as the intersection number, to the case $t=3$. The upper bound is tight, with equality holding only for the Tur'an graph $T(n,3)$. We also extend an algorithm of Scheinerman and Trenk (1999) to solve a weighted version of the $K_t$ clique cover problem on a superclass of chordal graphs. We also prove that the $K_t$ clique cover problem is NP-hard.

Recommendations

• scientific article; zbMATH DE number 3762108
• On the clique cover width problem
• scientific article; zbMATH DE number 617588
• Approximation Algorithms for the k-Clique Covering Problem
• Clique covers and coloring problems of graphs
• On clique coverings of complete multipartite graphs
• Covering the cliques of a graph with vertices
• A new upper bound for the clique cover number with applications

Cites work

• scientific article; zbMATH DE number 3582190 (Why is no real title available?)
• scientific article; zbMATH DE number 3253072 (Why is no real title available?)
• scientific article; zbMATH DE number 3185004 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A generalization of a theorem of Turán
• An upper bound for the Turán number \(t_3(n,4)\)
• Applications of edge coverings by cliques
• Correlation clustering
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• Covers in hypergraphs
• Extremal problems in graph theory
• On rigid circuit graphs
• On the fractional intersection number of a graph
• Reducibility among combinatorial problems
• The Complexity of Near-Optimal Graph Coloring
• The Representation of a Graph by Set Intersections
• Vertex elimination orderings for hereditary graph classes

Cited in

(5)

• A Turán-type generalization of Tuza's triangle edge cover problem
• A new upper bound for the clique cover number with applications
• Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs
• \(K_ i\)-covers. I: Complexity and polytopes
• The complexity of generalized clique covering

This page was built for publication: On the triangle clique cover and \(K_t\) clique cover problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2279271)