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.

  • $\begingroup$ I am curious, is there a practical application behind this problem ? Where does it come from ? $\endgroup$
    – Kuifje
    Jun 26, 2022 at 10:32
  • 1
    $\begingroup$ 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 ? $\endgroup$
    – Kuifje
    Jun 26, 2022 at 10:38
  • 2
    $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Jun 26, 2022 at 12:43
  • $\begingroup$ About the 2 objectives, I want the minimal number of colors and, for this number, I want the minimal number of cliques $\endgroup$
    – Jin Kazama
    Jun 27, 2022 at 12:10


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.