On the triangle clique cover and \(K_t\) clique cover problems

DOI10.1016/j.disc.2019.111627zbMath1429.05160arXiv1709.01590OpenAlexW2752765779MaRDI QIDQ2279271

Gregory J. Puleo, Hoang Dau, Olgica Milenković

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

intersection numbercommunity detectiongraph clusteringedge clique coverTuran graphtriangle clique cover

Mathematics Subject Classification ID

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

Related Items

Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs

Cites Work

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