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

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• Correlation clustering
• On rigid circuit graphs
• On the fractional intersection number of a graph
• 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
• 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 (1)

• Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Covering the cliques of a graph with vertices 👍 👎
• Approximation Algorithms for the k-Clique Covering Problem 👍 👎
• Clique covers and coloring problems of graphs 👍 👎
• On the complete width and edge clique cover problems 👍 👎
• On clique coverings of complete multipartite graphs 👍 👎
• A new upper bound for the clique cover number with applications 👍 👎

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)