New upper bounds on harmonious colourings

Keith Edwards, Colin McDiarmid

    Research output: Contribution to journalArticle

    25 Citations (Scopus)

    Abstract

    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
    Volume18
    Issue number3
    DOIs
    Publication statusPublished - 1994

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

  • Cite this