"Oriented colouring is a quite intuitive generalization of undirected colouring, yet the problem remains NP-hard even on digraph classes with bounded usual directed width measures. In light of this fact, one might ask whether new width measures are required for efficient dealing with this problem or whether further restriction of traditional directed width measures such as DAG-width would suffice. The K-width and DAG-depth measures (introduced by [Ganian et al, IWPEC09]) are ideal candidates for tackling this question: They are both closely tied to the cops-and-robber games which inspire and characterize the most renowned directed width measures, while at the same time being much more restrictive. In this paper, we look at the oriented colouring problem on digraphs of bounded K-width and of bounded DAG-depth."@en . "2"^^ . "9783642112652" . "New results on the complexity of oriented colouring on restricted digraph classes"@en . . "Springer-Verlag" . "Ganian, Robert" . "14330" . . . . . "12"^^ . "Directed graph; complexity; oriented colouring; DAG-depth"@en . "2010-01-01+01:00"^^ . "New results on the complexity of oriented colouring on restricted digraph classes" . "P(GA201/08/0308), P(GC201/09/J021), S" . "\u0160pindler\u016Fv ml\u00FDn" . . . "000280086900036" . "274759" . "Oriented colouring is a quite intuitive generalization of undirected colouring, yet the problem remains NP-hard even on digraph classes with bounded usual directed width measures. In light of this fact, one might ask whether new width measures are required for efficient dealing with this problem or whether further restriction of traditional directed width measures such as DAG-width would suffice. The K-width and DAG-depth measures (introduced by [Ganian et al, IWPEC09]) are ideal candidates for tackling this question: They are both closely tied to the cops-and-robber games which inspire and characterize the most renowned directed width measures, while at the same time being much more restrictive. In this paper, we look at the oriented colouring problem on digraphs of bounded K-width and of bounded DAG-depth." . . . "[7B63064EB386]" . "Berlin" . "SOFSEM 2010, Lecture Notes in Computer Science 5901" . "Hlin\u011Bn\u00FD, Petr" . "10.1007/978-3-642-11266-9_36" . . . "RIV/00216224:14330/10:00065874!RIV14-MSM-14330___" . "RIV/00216224:14330/10:00065874" . . . . . . . . . . "0302-9743" . "New results on the complexity of oriented colouring on restricted digraph classes" . "New results on the complexity of oriented colouring on restricted digraph classes"@en . "2"^^ .