Some Results on the Achromatic Number

N. Cairnie, K. Edwards

    Research output: Contribution to journalArticle

    31 Citations (Scopus)

    Abstract

    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
    Volume26
    Issue number3
    Publication statusPublished - 1997

    Fingerprint

    Achromatic number
    Integer
    Vertex Coloring
    Simple Graph
    Maximum Degree
    Adjacent
    NP-complete problem
    Graph in graph theory
    Color

    Cite this

    Cairnie, N. ; Edwards, K. / Some Results on the Achromatic Number. In: Journal of Graph Theory. 1997 ; Vol. 26, No. 3. pp. 129-136.
    @article{a7f40535aa654865a6b88f7b0de677af,
    title = "Some Results on the Achromatic Number",
    abstract = "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).",
    author = "N. Cairnie and K. Edwards",
    note = "Copyright 2004 Elsevier Science B.V., Amsterdam. All rights reserved.",
    year = "1997",
    language = "English",
    volume = "26",
    pages = "129--136",
    journal = "Journal of Graph Theory",
    issn = "0364-9024",
    publisher = "Wiley",
    number = "3",

    }

    Cairnie, N & Edwards, K 1997, 'Some Results on the Achromatic Number', Journal of Graph Theory, vol. 26, no. 3, pp. 129-136.

    Some Results on the Achromatic Number. / Cairnie, N.; Edwards, K.

    In: Journal of Graph Theory, Vol. 26, No. 3, 1997, p. 129-136.

    Research output: Contribution to journalArticle

    TY - JOUR

    T1 - Some Results on the Achromatic Number

    AU - Cairnie, N.

    AU - Edwards, K.

    N1 - Copyright 2004 Elsevier Science B.V., Amsterdam. All rights reserved.

    PY - 1997

    Y1 - 1997

    N2 - 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).

    AB - 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).

    UR - http://www.scopus.com/inward/record.url?scp=0031517582&partnerID=8YFLogxK

    M3 - Article

    VL - 26

    SP - 129

    EP - 136

    JO - Journal of Graph Theory

    JF - Journal of Graph Theory

    SN - 0364-9024

    IS - 3

    ER -