Some Results on the Achromatic Number

N. Cairnie; K. Edwards

Some Results on the Achromatic Number

N. Cairnie
, K. Edwards

Research output: Contribution to journal › Article › peer-review

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 language	English
Pages (from-to)	129-136
Number of pages	8
Journal	Journal of Graph Theory
Volume	26
Issue number	3
Publication status	Published - 1997

Cite this

@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",

year = "1997",

language = "English",

volume = "26",

pages = "129--136",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley",

number = "3",

}

TY - JOUR

T1 - Some Results on the Achromatic Number

AU - Cairnie, N.

AU - Edwards, K.

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 - https://www.scopus.com/pages/publications/0031517582

M3 - Article

AN - SCOPUS:0031517582

SN - 0364-9024

VL - 26

SP - 129

EP - 136

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

Some Results on the Achromatic Number

Abstract

Other files and links

Fingerprint

Cite this