On the complexity of path problems in properly colored directed graphs

Donatella Granata (), Behnam Behdani () and Panos M. Pardalos ()
Additional contact information
Donatella Granata: University of Rome “La Sapienza”
Behnam Behdani: University of Florida
Panos M. Pardalos: University of Florida

Journal of Combinatorial Optimization, 2012, vol. 24, issue 4, No 5, 459-467

Abstract: Abstract 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 $\mathcal{X}(G)$ stable subsets, where $\mathcal{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.

Keywords: Graph coloring; Complexity; Chromatic number; Longest path; Shortest path (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-011-9401-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:24:y:2012:i:4:d:10.1007_s10878-011-9401-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-011-9401-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().