**O. Aichholzer, F. Aurenhammer, T. Hackl, C. Huemer, A. Pilz, and
B. Vogtenhuber**

Deciding -colorability for general plane graphs is known to be an
NP-complete problem. However, for certain classes of plane graphs, like
triangulations, polynomial time algorithms exist. We consider the family of
pseudo-triangulations (a generalization of triangulations) and prove
NP-completeness for this class, even if the maximum face-degree is bounded to
four, or pointed pseudo-triangulations with maximum face degree five are
considered. As a complementary result, we show that for pointed
pseudo-triangulations with maximum face-degree four, a -coloring always
exists and can be found in linear time.