Multiple vertex coverings by cliques (Q4667797)

For positive integers \(m_1,\dots,m_k\), let \(f(m_1,\dots,m_k)\) be the minimum order of a graph whose edges can be colored with \(k\) colors such that every vertex is in a clique of cardinality \(m_i\), all of whose edges have the \(i\)th color for all \(i=1,2,\dots,k\). The value for \(k=2\) was determined by \textit{R. C. Entringer} et al. [J Graph Theory 24, 21--23 (1997; Zbl 0865.05051)]. Let \(f(m_1,m_2,\dots,m_k)=f_k(K_m)\) for \(m=m_1=m_2=\ldots=m_k\). There are several results concerning the parameter \(f(m_1,m_2,\dots,m_k)\) proved in this paper. Let us mention a few of them: \noindent (1) For fixed \(k\) and \(m\geq2\), \(2km-\mathcal O(\log m)\leq f_k(K_m)\leq2k(m-1)\). \noindent (2) For integers \(l,m,n\) with \(l,m,n\geq2\), it holds that \(f(l,m,n)\leq2(l+m+n-3)\). \noindent (3) For \(m\geq3\), we have \(f(m,2,2)=m+\lceil\sqrt{8(m-2)}\rceil\). \noindent (4) For integers \(l,m,n\) with \(l,m\geq2\), it holds that \(f(l,m,2)\leq2(l+m-2)\). \noindent (5) For \(l\geq2\) and \(m>l-2\sqrt{l-1}+1\) we have \(f(l,m,2)=f(l,m)=2(l+m-2)\). There are many open question mentioned in the paper, e.g. what is a general result for \(f(l,m,2)\).