On clique coverings of complete multipartite graphs

DOI10.1016/J.DAM.2019.09.014zbMATH Open1435.05159arXiv1809.01443OpenAlexW2980945783WikidataQ127017162 ScholiaQ127017162MaRDI QIDQ2309546FDOQ2309546

Authors: A. Davoodi, Dániel Gerbner, Abhishek Methuku, Máté Vizer 

Publication date: 1 April 2020

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

Abstract: A clique covering of a graph $G$ is a set of cliques of $G$ such that any edge of $G$ is contained in one of these cliques, and the weight of a clique covering is the sum of the sizes of the cliques in it. The sigma clique cover number $scc(G)$ of a graph $G$, is defined as the smallest possible weight of a clique covering of $G$. Let $K_t(d)$ denote the complete $t$-partite graph with each part of size $d$. We prove that for any fixed $dge2$, we have ${\displaystyle }$lim_{t ightarrow infty} scc(K_t(d))= frac{d}{2} tlog t.${\displaystyle }$ This disproves a conjecture of Davoodi, Javadi and Omoomi.

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

Recommendations

• Edge clique covering sum of graphs
• Clique covering of graphs
• Extremal clique coverings of complementary graphs
• Clique partitions and clique coverings
• scientific article; zbMATH DE number 1545697

zbMATH Keywords

clique coveringqualitatively independent familysigma clique covering

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Extremal set theory (05D05)

Cites Work

• Topics in Intersection Graph Theory
• Proof of a conjecture of Katona and Tarjan
• Pairwise balanced designs and sigma clique partitions
• On a problem of G. O. H. Katona and T. Tarján
• On the Decomposition of Graphs
• On generalized graphs
• The Representation of a Graph by Set Intersections
• Clique coverings and claw-free graphs
• Sperner capacities
• Local clique covering of claw-free graphs
• Edge clique covering sum of graphs

Cited In (10)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Clique covering and clique partition in generalizations of line graphs
• Clique numbers of graphs and irreducible exact \(m\)-covers of the integers
• Clique decompositions of multipartite graphs and completion of Latin squares
• On the triangle clique cover and \(K_t\) clique cover problems
• Title not available (Why is that?)
• Edge clique covering sum of graphs
• Clique Cover and Graph Separation
• Title not available (Why is that?)

This page was built for publication: On clique coverings of complete multipartite graphs

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