Christopher Duffy ; Gary MacGillivray ; Éric Sopena - A Study of $k$-dipath Colourings of Oriented Graphs

dmtcs:1520 - Discrete Mathematics & Theoretical Computer Science, February 1, 2018, Vol. 20 no. 1 - https://doi.org/10.23638/DMTCS-20-1-6
A Study of $k$-dipath Colourings of Oriented GraphsArticle

Authors: Christopher Duffy ORCID; Gary MacGillivray ; Éric Sopena

    We examine $t$-colourings of oriented graphs in which, for a fixed integer $k \geq 1$, vertices joined by a directed path of length at most $k$ must be assigned different colours. A homomorphism model that extends the ideas of Sherk for the case $k=2$ is described. Dichotomy theorems for the complexity of the problem of deciding, for fixed $k$ and $t$, whether there exists such a $t$-colouring are proved.


    Volume: Vol. 20 no. 1
    Section: Graph Theory
    Published on: February 1, 2018
    Accepted on: January 13, 2018
    Submitted on: August 3, 2017
    Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics,05C15, 05C20, 05C60,F.2.2,G.2.2
    Funding:
      Source : OpenAIRE Graph
    • Funder: Natural Sciences and Engineering Research Council of Canada

    Consultation statistics

    This page has been seen 640 times.
    This article's PDF has been downloaded 335 times.