• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

On the complexity of path problems in properly colored directed graphs

Journal of Combinatorial Optimization. 2012. Vol. 24. No. 4. P. 459-467.
Granata D., Behdani B., Pardalos P. M.

We address the complexity class of several problems related to finding a path in a properly colored directed graph. A properly colored graph is defined as a graph G whose vertex set is partitioned into X(G)  stable subsets, where X(G)  denotes the chromatic number of G. We show that to find a simple path that meets all the colors in a properly colored directed graph is NP-complete, and so are the problems of finding a shortest and longest of such paths between two specific nodes.