# Graph coloring problem while counting cliques

Let $$G$$ be a graph with a set of nodes $$V$$ and a set of edges $$E$$. Let $$G'$$ be a graph with the same set of nodes $$V$$ but a second set of edges $$E'$$.

For a set of nodes $$X\subset V$$, we denote $$f(X)$$ as the number of cliques (using the edges $$E'$$) when partitioning $$X$$ in cliques. More precisely, this partition is computed by recursively finding the biggest clique. So, if $$X_1$$ is the biggest clique in $$X$$ and $$X_2$$ is the biggest clique in $$X\setminus X_1$$ and so on, we have $$X=X_1\cup X_2\cup\cdots\cup X_k$$ and $$f(X) = k$$.

Now, I want to color $$G$$ (using the set of edges $$E$$ and not $$E'$$) with the minimal number of colors such that, writing this partitioning of colors as $$V = V_1 \cup\cdots\cup V_m$$ we minimize $$f(V_1) + \cdots+f(V_m)$$.

I'm stuck on this problem, any hint is precious :)

Right now, I have tried to colorize the graph node by node (with the DSATUR heuristic) and when there are different possible colors, I compute $$f$$ for each choice and choose the one that minimizes $$f$$. But it's way too slow.

• I am curious, is there a practical application behind this problem ? Where does it come from ? Jun 26, 2022 at 10:32
• Also, if my understanding is correct, you are dealing with 2 objectives simultaneously : the number of color of classes with respect to $(V,E)$, and the total number of cliques with respect to $E'$ in each color class. How do you weigh each of these objectives ? And does it make sense to do that ? Jun 26, 2022 at 10:38
• If there are ties for the biggest clique, the value of $f$ can depend on which one you choose. For example, a path on four nodes can yield $f=2$ or $f=3$. Jun 26, 2022 at 12:43
• About the 2 objectives, I want the minimal number of colors and, for this number, I want the minimal number of cliques Jun 27, 2022 at 12:10