Gnome and KDE are desktop environments. They are not required for a graphical login, although given the high share of good frequently used software from both Gnome and KDE it can be a bit harsh being without them being installed.
For a minimalistic approach, the metapackage x-window-system provides the very basics of the graphical environment (the X Window System installed is XFree86 on Debian 3.1 'sarge' and X.Org on Debian testing ('etch') and unstable ('sid')) including a graphical login using xdm as the display manager (xdm might not be the prettiest around and lacks a bunch of options, but it does what it is supposed to do), and then add window managers of your choice.
Example: installing x-window-system and both the Enlightenment and AfterStep window managers:
Code:
apt-get install x-window-system enlightenment afterstep
If you wish to install Gnome or KDE you can do so by e.g.
Gnome and the gdm display manager:
Code:
apt-get install gnome gdm
(or just apt-get install gnome-desktop-environment gdm if you want a bit leaner installation)
KDE and the kdm display manager:
Code:
apt-get install kde kdm