On the Complexity of Digraph Colourings and Vertex Arboricity
It has been shown by Bokal et al. that deciding 2-colourability of digraphs is an NP-complete problem. This result was later on extended by Feder et al. to prove that deciding whether a digraph has a circular $p$-colouring is NP-complete for all rational $p>1$. In this paper, we consider the complex...
Αποθηκεύτηκε σε:
| Κύριοι συγγραφείς: | , , |
|---|---|
| Μορφή: | Artigo |
| Γλώσσα: | Inglês |
| Έκδοση: |
Discrete Mathematics & Theoretical Computer Science
2020-01-01
|
| Σειρά: | Discrete Mathematics & Theoretical Computer Science |
| Θέματα: | |
| Διαθέσιμο Online: | https://dmtcs.episciences.org/5140/pdf |
| Ετικέτες: |
Δεν υπάρχουν, Καταχωρήστε ετικέτα πρώτοι!
|