A three color problem
Gordon D. Simons, Yuxuan Yao · 1991
It is well-known that the problem of determining whether a planar map is three-colorable is NP-complete. There are also several isolated results on three-colorability for certain classes of maps. Herein, we consider. a new class of maps that consists of those involving lines and half-lines. It is shown that such maps are three-colorable if they satisfy a simple condition. An extension to curved lines is also considered.