On two q-ary n-cube coloring problems

2015/10/28 by Zhe Han, Han, Z., Ming‐Hui Lu +1
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1510.08168

openalex publication_date 2015/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let χ'_d(n,q) (resp. χ_d(n,q)) denote the minimum number of colors necessary to color a q-ary n-cube so that no two vertices that are at a distance at most d (resp. exactly d) get the same color. These two problems were proposed in the study of scalability of optical networks. In this paper, we provide upper and lower bounds on χ'_d(n,q) and χ_d(n,q) when q is a prime power.

Related

• New Results on Two Hypercube Coloring Problems
• Two coloring problems on matrix graphs
• The chromatic number of the square of the 8-cube
• Extending edge-colorings of distance-2 matchings in the hypercube
• A coloring of the square of the 8-cube with 13 colors