Wolfram Research

Function Repository Resource:

ValidGraphColoring

Source Notebook

Check if the given graph coloring is valid

Contributed by: Jongwan Kim

ResourceFunction["ValidGraphColoring"][graph,coloring]

gives True if no two adjacent vertices in graph have the same color as specified by coloring.

Details and Options

In ResourceFunction["ValidGraphColoring"][graph,coloring], coloring can be a list of actual colors or numbers indicating distinct colors.
The value for graph must be an instance of a graph, not an adjacency matrix or list.

Examples

Basic Examples

Determine if the given coloring of a complete graph with two vertices is valid:

In[1]:=
ResourceFunction["ValidGraphColoring"][\!\(\*
GraphicsBox[
NamespaceBox["NetworkGraphics",
DynamicModuleBox[{Typeset`graph = HoldComplete[
Graph[{1, 2}, {Null, 
SparseArray[
         Automatic, {2, 2}, 0, {
          1, {{0, 1, 2}, {{2}, {1}}}, Pattern}]}, {
        VertexSize -> {Medium}}]]}, 
TagBox[GraphicsGroupBox[GraphicsComplexBox[{{1., 0.}, {-1., 0.}}, {
{Hue[0.6, 0.7, 0.5], Opacity[0.7], 
{Arrowheads[0.], ArrowBox[{1, 2}, 0.2]}}, 
{Hue[0.6, 0.2, 0.8], EdgeForm[{GrayLevel[0], Opacity[0.7]}], DiskBox[1, 0.2], DiskBox[2, 0.2]}}]],
MouseAppearanceTag["NetworkGraphics"]],
AllowKernelInitialization->False]],
DefaultBaseStyle->{
     "NetworkGraphics", FrontEnd`GraphicsHighlightColor -> Hue[0.8, 1., 0.6]},
FormatType->TraditionalForm,
FrameTicks->None]\), {1, 2}]
Out[1]=

Applications

Find the valid colorings of a graph:

In[2]:=
graph = RandomGraph[{4, 3}, VertexSize -> Medium, VertexLabels -> Automatic]
Out[2]=

Determine the minimum number of colors to color the graph:

In[3]:=
chrom = MinValue[{z, z > 0 && ChromaticPolynomial[graph, z] > 0}, z, Integers]
Out[3]=
In[4]:=
colorings = Tuples[Table[i, {i, 1, chrom}], VertexCount[graph]]
Out[4]=
In[5]:=
sols = Select[colorings, ResourceFunction["ValidGraphColoring"][graph, #] &]
Out[5]=

Resource History

License Information