On the partition and coloring of a graph by cliques (Q687122)

A clique partition \(P\) of a graph \(G\) is a partition of \(E(G)\) whose classes induce complete subgraphs (cliques) of \(G\). The norm of \(P\) is the order of the greatest clique in \(P\). Denote by \(\text{cp}(G)\) the minimal cardinality of a clique partition. Given a set \(C\) of \(h\) ``colors'', an \(h\)-coloring of \(P\) in \(G\) is a mapping from \(P\) to \(C\), such that cliques sharing a vertex have different colors. For \(2\leq k\leq \Delta(G)\) define \(\chi_ k(G)\) as the smallest \(h\) such that there is a partition \(P\) with norm at most \(k\) and having an \(h\)-coloring. Upper and lower bounds of \(\text{cp}(G)\) and \(\chi_ k(G)\) are given for several graphs \(G\). In some cases, the exact value of \(\chi_ k(G)\) is determined: e.g., if \(m=\lceil\sqrt n\rceil\) is the order of an affine plane, then \(\chi_ k(K_ n)= m+1\) whenever \(m\leq k\leq n-1\).