The Wikipedia article on Equitable coloring states that

A polynomial time algorithm is known for equitable coloring of split graphs.

The referred paper also seems to achive the proposed polynomial time, as far as my understanding goes.

One the other hand some other published paper states the following:

EQUITABLE COLORING of the disjoint union of split graphs parameterized by the number of colors is $W[1]$-hard.

Where the disjoint union is defined as follows: The disjoint union of two graphs $G\cup H$ is a graph such that $V (G\cup H) = V (G)\cup V (H)$and $E(G \cup H) = E(G) \cup E(H)$.

One the one hand a poly-time algorithm seems like a great result for split graphs, on the other hand we have a $W[1]$-hard problem for the disjoint union of such graphs. This seems odd to me as the disjoint union is only a couple of split graphs combined to one bigger graph (in which itself each split graph isnt even connected).

As far as my understanding goes we could just color each individual split-graph of the union with the poly-time algorithm and we would still achive some optimal result in polynomial time.

What am I missing here? What is the exact difference that leads to this "jump" in complexity? And most importantly what is wrong in my "attempt" to get a poly-time algorithm for equitable coloring "disjoint union of split graphs"?

  • $\begingroup$ I want to add some thoughts of mine. Any corrections or confirmation will be appriciated. Could it be that the poly-time result is only possible if we are looking for a equitable $\Delta(G)$-coloring. (Where $\Delta$ is the max degree). And the hardness result is valid if we are looking for some arbitrary equitable $k$-coloring. (where $k$ isn't limited to $k=\Delta(G)$)? $\endgroup$
    – Felix
    Dec 11 '21 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.