5
$\begingroup$

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] -> %]}]

enter image description here

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).

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – David G. Stork
    Aug 28 at 16:40
  • $\begingroup$ @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. $\endgroup$
    – licheng
    Aug 28 at 16:47

1 Answer 1

Reset to default
6
$\begingroup$

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 -> 
      Thread[vertsforColoring[[i]] -> colorings[[i]]]}], {i, 
    Length@colorings}]
  )

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

findmaxKColoring[g, 4]

enter image description here

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Nice implementation and visualization ($+1$). $\endgroup$
    – David G. Stork
    Aug 28 at 18:34
  • $\begingroup$ 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. $\endgroup$
    – licheng
    Aug 31 at 2:15

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.