✦ LIBER ✦

Some results on the achromatic number

✍ Scribed by Cairnie, Niall; Edwards, Keith

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 106 KB
Volume: 26
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199711)26:3<129::aid-jgt3>3.0.co;2-t

No coin nor oath required. For personal study only.

✦ Synopsis

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 ( k 2 ) ≤ 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 0 = N 0 (d, ) such that if G is a graph with maximum degree at most d, and m ≥ N 0 edges, then (1 -)q(m) ≤ ψ(G) ≤ q(m).

📜 SIMILAR VOLUMES

On the Achromatic Number of Hypercubes

✍ Yuval Roichman 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 96 KB

The achromatic number of a finite graph G, (G), is the maximum number of independent sets into which the vertex set may be partitioned, so that between any two parts there is at least one edge. For an m-dimensional hypercube P m 2 we prove that there exist constants 0<c 1 <c 2 , independent of m, su

Approximation Algorithms for the Achroma

Approximation Algorithms for the Achromatic Number

✍ Amitabh Chaudhary; Sundar Vishwanathan 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 108 KB

The achromatic number for a graph G = V E is the largest integer m such that there is a partition of V into disjoint independent sets V 1 V m such that for each pair of distinct sets V i , V j , V i ∪ V j is not an independent set in G. Yannakakis and Gavril (1980, SIAM J. Appl. Math. 38, 364-372) p

Some results on generalized exponents

✍ Neufeld, Stewart; Shen, Jian 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 241 KB

A digraph G = (V, E) is primitive if, for some positive integer k, there is a u → v walk of length k for every pair u, v of vertices of V . The minimum such k is called the exponent of G, denoted exp(G). The exponent of a vertex u ∈ V , denoted exp(u), is the least integer k such that there is a u →

Some results on linear arboricity

✍ Filip Guldan 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB

Some Results on Radical Extensions

✍ F.B. Mora; W.Y. Velez 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 265 KB

On Some Results Concerning the Reduite a

On Some Results Concerning the Reduite and Balayage

✍ Valentin Grecea 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 179 KB 👁 1 views