### Abstract

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 |

### Fingerprint

### Cite this

*Journal of Graph Theory*,

*26*(3), 129-136.

}

*Journal of Graph Theory*, vol. 26, no. 3, pp. 129-136.

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

Research output: Contribution to journal › Article

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 -