| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 421425 | Discrete Applied Mathematics | 2007 | 11 Pages |
Abstract
In this paper we deal with the arc ranking problem of directed graphs. We give some classes of graphs for which the arc ranking problem is polynomially solvable. We prove that deciding whether χr′(G)⩽6, where G is an acyclic orientation of a 3-partite graph is an NP-complete problem. In this way we answer an open question stated by Kratochvil and Tuza in 1999.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Dariusz Dereniowski,