Some Results on the Achromatic Number

N. Cairnie, K. Edwards

    Research output: Contribution to journalArticlepeer-review

    41 Citations (Scopus)


    Let G be a simple graph. The achromatic number ?(G) is the largest number of colors possible in a proper vertex coloring of G in which each pair of colors is adjacent somewhere in G. For any positive integer m, let q(m) be the largest integer k such that () = m. We show that the problem of determining the achromatic number of a tree is NP-hard. We further prove that almost all trees T satisfy ?(T) = q(m), where m is the number of edges in T. Lastly, for fixed d and ? > 0, we show that there is an integer N = N(d, ?) such that if G is a graph with maximum degree at most d, and m = N edges, then (1 - ?)q(m) = ?(G) = q(m).
    Original languageEnglish
    Pages (from-to)129-136
    Number of pages8
    JournalJournal of Graph Theory
    Issue number3
    Publication statusPublished - 1997


    Dive into the research topics of 'Some Results on the Achromatic Number'. Together they form a unique fingerprint.

    Cite this