On the triangle clique cover and K_t clique cover problems

DOI10.1016/J.DISC.2019.111627zbMATH Open1429.05160arXiv1709.01590OpenAlexW2752765779MaRDI QIDQ2279271FDOQ2279271

Gregory J. Puleo, Hoang Dau, Olgica Milenkovic

Publication date: 12 December 2019

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

Recommendations

• scientific article
• 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
• On the complete width and edge clique cover problems
• On the complete width and edge clique cover problems
• Covering the cliques of a graph with vertices
• A new upper bound for the clique cover number with applications

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)

Cites Work

• Reducibility among Combinatorial Problems
• Correlation clustering
• Title not available (Why is that?)
• On rigid circuit graphs
• On the fractional intersection number of a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• An upper bound for the Turán number \(t_3(n,4)\)
• Applications of edge coverings by cliques
• The Complexity of Near-Optimal Graph Coloring
• Title not available (Why is that?)
• The Representation of a Graph by Set Intersections
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• A generalization of a theorem of Turán
• Covers in hypergraphs
• Vertex elimination orderings for hereditary graph classes
• Extremal problems in graph theory

Cited In (3)

• \(K_ i\)-covers. I: Complexity and polytopes
• The complexity of generalized clique covering
• Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs

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)