A Coloring Problem in Hamming Spaces

Author： Östergård P.R.J.  

Publisher： Academic Press

ISSN： 0195-6698

Source： European Journal of Combinatorics, Vol.18, Iss.3, 1997-04, pp. : 303-309

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

TheR-domatic number of a graph is the maximum number of colors that can be used to color the vertices of the graph so that all vertices of the graph have at least one vertex of each color within distanceR.In this paper the problem of determining theR-domatic number of then-cube,P(n,R), is considered. The valueP(6,1) =5 is settled, and a conjecture by Laborde thatP(n, 1)≈n asntends to infinity is proved. Best known upper and lower bounds on theR-domatic number of then-cube are given forn≤16 andR≤7.

Related content

Semigroups and the Generalized Road Coloring Problem

By Budzban Greg  

Semigroup Forum, Vol. 69, Iss. 2, 2004-08 ,pp. : 201-208 (8)

Springer Publishing Company

Access to resources Recommend Favorite

The Monge Problem in Banach Spaces

By Heinich Henri  

Journal of Theoretical Probability, Vol. 19, Iss. 2, 2006-06 ,pp. : 509-534 (26)

Springer Publishing Company

Access to resources Recommend Favorite

Completely Simple Semigroups, Lie Algebras, and the Road Coloring Problem

By Budzban Greg   Feinsilver Philip  

Semigroup Forum, Vol. 74, Iss. 2, 2007-04 ,pp. : 206-226 (21)

Springer Publishing Company

Access to resources Recommend Favorite

On the implicit Darboux problem in Banach spaces

By  

Bulletin of the Australian Mathematical Society, Vol. 56, Iss. 1, 1997-08 ,pp. : 149-156 (8)

Cambridge University Press

Access to resources Recommend Favorite

Metrizable (LF)-spaces, (db)-spaces, and the separable quotient problem

By  

Bulletin of the Australian Mathematical Society, Vol. 23, Iss. 1, 1981-02 ,pp. : 65-80 (16)

Cambridge University Press

Access to resources Recommend Favorite