International Journal of Mathematics and Mathematical Sciences
Volume 2011 (2011), Article ID 961649, 7 pages
doi:10.1155/2011/961649
Research Article

Improved Bounds for Radio 𝑘 -Chromatic Number of Hypercube 𝑄 𝑛

Department of Mathematics, IIT Kharagpur, Kharagpur 721302, India

Received 13 December 2010; Accepted 18 February 2011

Academic Editor: Brigitte Forster-Heinlein

Copyright © 2011 Laxman Saha et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

A number of graph coloring problems have their roots in a communication problem known as the channel assignment problem. The channel assignment problem is the problem of assigning channels (nonnegative integers) to the stations in an optimal way such that interference is avoidedas reported by Hale (2005). Radio 𝑘 -coloring of a graph is a special type of channel assignment problem. Kchikech et al. (2005) have given a lower and an upper bound for radio 𝑘 -chromatic number of hypercube 𝑄 𝑛 , and an improvement of their lower bound was obtained by Kola and Panigrahi (2010). In this paper, we further improve Kola et al.'s lower bound as well as Kchikeck et al.'s upper bound. Also, our bounds agree for nearly antipodal number of 𝑄 𝑛 when 𝑛 2 (mod 4).