New upper bounds on harmonious colourings

Keith Edwards, Colin McDiarmid

    Research output: Contribution to journalArticlepeer-review

    27 Citations (Scopus)


    We present an improved upper bound on the harmonious chromatic number of an arbitrary graph. We also consider “Fragmentable” classes of graphs (an example is the class of planar graphs) which are, roughly speaking, graphs which can be decomposed into bounded sized components by removing a small proportion of the vertices. We show that for such graphs of bounded degree the harmonious chromatic number is close to the lower bound (2m)^1/2 , where m is the number of edges.
    Original languageEnglish
    Pages (from-to)257-267
    Number of pages11
    JournalJournal of Graph Theory
    Issue number3
    Publication statusPublished - 1994


    Dive into the research topics of 'New upper bounds on harmonious colourings'. Together they form a unique fingerprint.

    Cite this