Article ID Journal Published Year Pages File Type
6872017 Discrete Applied Mathematics 2016 9 Pages PDF
Abstract
Our result defines a P versus NP-complete dichotomy with respect to the maximum degree Δ(G): OCNk is polynomial if Δ(G)<3 and NP-complete if Δ(G)≥3, since it is known that OCN3 is in P, and that OCNk is in P when the underlying graph has Δ(G)≤2.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs
Authors
, , , ,