Path coloring

From formulasearchengine
Jump to navigation Jump to search

In graph theory, path coloring usually refers to one of two problems:

In both the above problems, the goal is usually to minimise the number of colors used in the coloring. In different variants of path coloring, may be a simple graph, digraph or multigraph.


  • [1] The Complexity of Path Coloring and Call Scheduling by Thomas Erlebach and Klaus Jansen
  • [2] A compendium of NP optimization problems by Viggo Kann (problem: Minimum Path Coloring)