Try

function wpse46583_save($post_id,$post) {
     // verify this is not an auto save routine. 
     if ( defined(\'DOING_AUTOSAVE\') && DOING_AUTOSAVE ) return;

     //You should check nonces and permissions here
      if ( !current_user_can( \'edit_page\', $post_id )
           return;

     //Get category slugs associated with post
     $cats =get_the_category($post_id);

     if(empty($cats)){
        //No category assigned - do something here.
     }

     return;
}
add_action(\'save_post\',\'wpse46583_save\',10,2);