Function Repository Resource:

ValidGraphColoring

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 (1)

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