Harmonious chromatic number of directed graphs

    Research output: Contribution to journalArticlepeer-review

    10 Citations (Scopus)

    Abstract

    We consider the extension to directed graphs of the concepts of harmonious colouring and complete colouring. We give an upper bound for the harmonious chromatic number of a general directed graph, and show that determining the exact value of the harmonious chromatic number is NP-hard for directed graphs of bounded degree (in fact graphs with maximum indegree and outdegree 2); the complexity of the corresponding undirected case is not known. We also consider complete colourings, and show that in the directed case the existence of a complete colouring is NP-complete. We also show that the interpolation property for complete colourings fails in the directed case.
    Original languageEnglish
    Pages (from-to)369-376
    Number of pages8
    JournalDiscrete Applied Mathematics
    Volume161
    Issue number3
    DOIs
    Publication statusPublished - 2013

    Fingerprint

    Dive into the research topics of 'Harmonious chromatic number of directed graphs'. Together they form a unique fingerprint.

    Cite this