coreutils отмечен Essential: yes, поэтому он всегда включается в установку, а dpkg предупреждает вас довольно неосведомленным образом, если вы попытаетесь удалить его. Пакеты не должны декларировать зависимости от необходимых пакетов, если только им не нужна конкретная версия (например, dpkg (другой существенный пакет) зависит от coreutils (>= 5.93-1) в Ubuntu 10.04).