As far as I can tell, there is no relation between host (dom0) and guest (domU). For dom0, you can even use NetBSD or OpenSolaris, while running a Linux domU. The kernels used need to have the appropriate modifications, however.
For Linux, the dom0 server patches have not been incorporated in the kernel. The last kernel with those patches is 2.6.18, but you can find a kernel with patches readily applied until about 2.6.24 (Ubuntu 8.04 can be a dom0). Patches for newer kernels (if available) have to be applied manually and you have to recompile the kernel. Also, there is now the transition to Xen4, which it seems it will integrate better with Linux.
On the other hand, the patches for the domU have been incorporated into the mainline kernel since 2.6.23, so any recent kernel can be a domU. It is just a matter if the distribution you are using has the package for it.
There is actually a potential dependency between host and guest, i.e. the guest kernel may be stored in the host disk (the traditional way), hence you cannot upgrade the kernel, the hosting company has to do it for you, unless they use