Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Publication
Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
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 d >= 2, we have lim(t ->infinity) scc(K-t(d)) = d/2t log t. This disproves a conjecture of Davoodi et al. (2016). (C) 2019 Elsevier B.V. All rights reserved.