# Find a maximum $k$-colorable subgraph

For a given graph, the Maximum $$k$$-Colorable Subgraph Problem is the problem of determining the largest set of vertices of the graph that can be colored using $$k$$ distinct colors such that adjacent vertices, if colored, are assigned different colors. This problem is NP-hard for general graphs.

[1] Lewis, J. M., and M. Yannakakis, The node-deletion problem for hereditary properties is NP-Complete, J. of Comp. System Sci., 20 (1980), pp. 219-230.

I know that the VertexChromaticNumber or FindVertexColoring is available in Mathematica, but I haven't come across the functionality mentioned above (perhaps it exists, but I haven't seen it)

For example, we consider a small graph with chromatic number 5.

g = Graph[ImportString["ORo?????ENDuFsW{QmF~~", "Graph6"],
GraphLayout -> "CircularEmbedding"];
VertexChromaticNumber[g]
FindVertexColoring[g, {White, Red, Green, Blue, Purple}];
Annotate[g, {VertexStyle -> Thread[VertexList[g] -> %]}]


If we use $$k$$ (where $$k\le 4$$) distinct colors, then can we determine the maximum $$k$$-colorable subgraph in $$G$$? I haven't found the corresponding algorithm yet (there might be one).

• An inefficient, near brute-force method is to find all subgraphs larger than size 4, computer their chromatic numbers, and select the subgraph with the largest such number. The coding is fairly straightforward, but this is very inefficient. Aug 28 at 16:40
• @DavidG.Stork Just now, I realized that for this graph, the maximum 4-colorable problem is somewhat simple, as there exists a coloring that only colors a single vertex. Therefore, with 4 colors, the maximum number of colored vertices is the total number of vertices minus 1. We can look for more generally moderate-sized examples, as we are considering a relatively general problem. Aug 28 at 16:47

Implementing David G. Stork's comment, this produces a graphic of all the maximal subgraphs that can be colored with $$k$$ colors. This is pretty rough and will probably get very slow for large vertex count graphs:

findmaxKColoring[g_, k_] :=
(
colored = {};
n = VertexCount[g];
While[colored == {},
subVerts = Subsets[VertexList[g], {n}];
subGraphs = Subgraph[g, #] & /@ subVerts;
colored =
Flatten[Position[VertexChromaticNumber /@ subGraphs, k]];
n--;
];
SeedRandom[5];
rc = RandomColor[k];
colorings = FindVertexColoring[#, rc] & /@ subGraphs[[colored]];
vertsforColoring = subVerts[[colored]];
Table[Annotate[
g, {VertexStyle ->
Length@colorings}]
)


With your graph we get 11 unique subgraphs with 15 vertices each that can be colored with 4 colors:

findmaxKColoring[g, 4]


Looking at a graph with a much larger VertexChromaticNumber, like CompleteGraph[16] shows how slow this can be though:

{timing, res} =
AbsoluteTiming[findmaxKColoring[CompleteGraph[16], 4]];
timing
(*15.2966*)


This produces Binomial[16,4] = 1820 subgraphs with 4 vertices that can be colored with 4 colors.

Maybe you are interested in just one example for a given graph of a maximal subgraph, not all possible maximal subgraphs? That could make things a little faster, as we can just take one Subgraph at a time and stop once we find one that satisfies the k-coloring.

• Nice implementation and visualization ($+1$). Aug 28 at 18:34
• The problem of determining chromatic number can be transformed into an integer programming problem. Naturally, this problem may likely be transformed as well. Of course, your approach is sufficiently effective for small graphs. Aug 31 at 2:15