79352216

Date: 2025-01-13 12:45:17
Score: 1.5
Natty:
Report link

This problem is called "precoloring" and, like node coloring, is NP-hard. You can construct (possibly approximate) solutions to this problem by making modifications to the graph and then running a standard node colouring algorithm. I've included a screenshot of the relevant section of my book below, which explains how to do this.

Alternatively, the GCol Python library has functions for coloring graphs that have precolored nodes.

Reference: Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5

Precoloring problem

Reasons:
  • No code block (0.5):
  • Low reputation (1):
Posted by: Rhyd Lewis