✦ LIBER ✦

On the Achromatic Number of Hypercubes

✍ Scribed by Yuval Roichman

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 96 KB
Volume: 79
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2000.1955

No coin nor oath required. For personal study only.

✦ Synopsis

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, such that c 1 (m2 m&1 ) 1Â2

(P m 2 ) c 2 (m2 m&1 ) 1Â2 .

📜 SIMILAR VOLUMES

Some results on the achromatic number

✍ Cairnie, Niall; Edwards, Keith 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 106 KB

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 dete

Achromatic number of fragmentable graphs

✍ Keith Edwards 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB

## Abstract A __complete coloring__ of a simple graph __G__ is a proper vertex coloring such that each pair of colors appears together on at least one edge. The __achromatic number__ ψ(__G__) is the greatest number of colors in such a coloring. We say a class of graphs is fragmentable if for any po

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

An improved upper bound on the crossing

An improved upper bound on the crossing number of the hypercube

✍ Luerbio Faria; Celina Miraglia Herrera de Figueiredo; Ondrej Sýkora; Imrich Vrt' 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB

## Abstract We draw the __n__‐dimensional hypercube in the plane with ${5\over 32}4^{n}-\lfloor{{{{n}^{2}+1}\over 2}}\rfloor {2}^{n-2}$ crossings, which improves the previous best estimation and coincides with the long conjectured upper bound of Erdös and Guy. © 2008 Wiley Periodicals, Inc. J Graph

w-Rabin numbers and strong w-Rabin numbe

w-Rabin numbers and strong w-Rabin numbers of folded hypercubes

✍ Cheng-Nan Lai; Gen-Huey Chen 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 179 KB

Randomized Selection on the Hypercube

✍ Sanguthevar Rajasekaran 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 258 KB

In this paper, we present randomized algorithms for selection on the hypercube. We identify two variants of the hypercube, namely, the sequential model and the parallel model. In the sequential model, any node at any time can handle only communication along a single incident edge, whereas in the par