Winfried Hochstättler ; Felix Schröder ; Raphael Steiner - On the Complexity of Digraph Colourings and Vertex Arboricity

dmtcs:5140 - Discrete Mathematics & Theoretical Computer Science, January 21, 2020, vol. 22 no. 1 - https://doi.org/10.23638/DMTCS-22-1-4
On the Complexity of Digraph Colourings and Vertex ArboricityArticle

Authors: Winfried Hochstättler ; Felix Schröder ORCID; Raphael Steiner ORCID

    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 complexity of corresponding decision problems for related notions of fractional colourings for digraphs and graphs, including the star dichromatic number, the fractional dichromatic number and the circular vertex arboricity. We prove the following results: Deciding if the star dichromatic number of a digraph is at most $p$ is NP-complete for every rational $p>1$. Deciding if the fractional dichromatic number of a digraph is at most $p$ is NP-complete for every $p>1, p \neq 2$. Deciding if the circular vertex arboricity of a graph is at most $p$ is NP-complete for every rational $p>1$. To show these results, different techniques are required in each case. In order to prove the first result, we relate the star dichromatic number to a new notion of homomorphisms between digraphs, called circular homomorphisms, which might be of independent interest. We provide a classification of the computational complexities of the corresponding homomorphism colouring problems similar to the one derived by Feder et al. for acyclic homomorphisms.


    Volume: vol. 22 no. 1
    Section: Graph Theory
    Published on: January 21, 2020
    Accepted on: November 16, 2019
    Submitted on: January 30, 2019
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 1567 times.
    This article's PDF has been downloaded 323 times.