# Graph coloring with fixed-size color classes

I'm interested in coloring a graph, but with slightly different objectives than the standard problem. It seems like the focus of most graph-coloring algorithms (DSATUR etc) is to minimize the number of color classes used.

My goal, in contrast, is to maximize the number of color classes of fixed size N.

As a concrete example, say I have a graph with 100 nodes, and I'd like to color the graph with color classes of size N = 30. With an optimal algorithm and the right graph, I could find 3 such groups that color 90 total nodes, with 10 nodes left over. A lesser algorithm might only produce 2 such groups, with 40 nodes left over that cannot be colored with a size-30 color class.

I figure I can solve this problem with a Greedy Algorithm, but it won't be optimal. Or I could model this in a constraint solver, but it might not employ some clever graph-specific tricks that could come in handy.

Does this specific problem have a name? Or an established algorithm to solve it? Thank you!

EDIT:

It was rightfully pointed out that my question is ambiguous! I can explain much more thoroughly, my apologies for the confusion.

First, let me define the size of a color class. I've seen this terminology elsewhere but might be using it incorrectly. The size of a color class is the number of nodes assigned to that color. I will denote this: size(C_i) = <number of nodes colored C_i>.

Now, to define a fixed size color class. This is a color class with size N. To use the example above, I'm interested in colorings with colors such that size(C_i) = 30.

As far as the optimization objective: I want to color a graph to maximize the number of size-30 color classes. If you'll permit me some Python pseudocode:

n_size_30_colors = len([c for c in colors if size(c) == 30])
maximize(n_size_30_colors)



To complete the example, take these two possible colorings of a graph with 100 nodes. Each number represents the number of nodes colored by that color:

Coloring 1: {55, 25, 20} (n_size_30_colors = 0)
Coloring 2: {30, 30, 20, 20} (n_size_30_colors = 2)
Coloring 3: {30, 30, 30, 10} (n_size_30_colors = 3)


Even though Coloring 1 uses fewer colors, Coloring 3 is optimal because it returns the most size-30 color classes. The size-55 color class in Coloring 1 is "wasteful" in that those 25 extra nodes are not useful; an optimal solution for this problem would distribute those nodes to other color classes, hopefully yielding more size-30 colors.

I hope this clarifies things somewhat, and thanks again!

• Welcome to CS.SE! What is meant by "maximize the number of color classes of fixed size N"? That sounds to me like it is contradictory; on the one hand, you want to maximize the number of colors, on the other hand it is fixed. I suspect I am not understanding what you have in mind. What's meant by the "size" of a "color class"? I'm also confused by "nodes left over"; normally in graph coloring we require to assign a color to each node. Can you give a careful specification of the task, i.e., the inputs to the algorithm and what output it should produce? Can you edit?
– D.W.
Nov 15, 2020 at 7:04
• Thank you for the helpful feedback D.W! I've added an edit, I hope it helps. Nov 15, 2020 at 21:04
• Some bad news: This problem is NP-hard, since Independent Set can be trivially reduced to it. A graph contains an IS of size $k$ iff treating it as an instance of your problem with $N=k$ gives a solution $\ge 1$. Nov 15, 2020 at 22:14

This problem is NP-hard: it is at least as hard as independent set. In particular, if you want to know whether there exists an independent set of size $$N$$, ask for a coloring with as many colors of size $$N$$; if you find any coloring where a single color occurs $$N$$ times, you know there's an independent set of size $$N$$. So, you should not expect any efficient algorithm for this problem that works on all problem instances.
One plausible approach is to use a ILP solver. You can define zero-or-one variables $$x_{v,c}$$, where $$x_{v,c}=1$$ means that vertex $$v$$ is assigned color $$c$$. Then it is easy to express the requirement that a color $$c$$ be assigned to exactly $$N$$ vertices: we require $$\sum_{v \in V} x_{v,c} = N$$. The constraint that two adjacent vertices $$v,w$$ be assigned different colors can be expressed by $$x_{v,c} + x_{w,c} \le 1$$ for all $$c$$, and that each vertex $$v$$ receive a color by $$\sum_c x_{v,c} = 1$$. Without loss of generality, to test whether it is possible to have $$k$$ colors be assigned to $$N$$ vertices, you can constrain the first $$k$$ colors to have $$N$$ vertices and put no constraints on the remaining colors. Then, use binary search on $$k$$ to find the largest $$k$$ for which a solution exists.
Another plausible approach is to use a SAT solver. You could define variables $$x_{v,c}$$, where if $$x_{v,c}$$ is true then vertex $$v$$ is assigned color $$c$$, and express your constraints in SAT. You can require that color $$c$$ be assigned to exactly $$N$$ vertices, by requiring that $$N$$ out of the variables $$x_{\cdot,c}$$ are set to true (see Encoding 1-out-of-n constraint for SAT solvers and links for methods). Otherwise, this is similar to using an ILP solver.
These might work if $$N$$ is small enough and the graph is small enough, but eventually will run into exponential behavior once the problem gets large enough.