Are there any references that address the following (open?) questions:
1) Is there an algorithm that 4-colors any planar graph of maximal degree at most 5 in linear time?
2) What is the largest number d for which there exist an algorithm that 4-colors any planar graph of maximal degree at most d in linear time?
3) Is every planar graph of maximal degree 5 or less 4-choosable?
4) What is the largest number d for which every planar graph of maximal degree at most d is 4-choosable?
Comments: For (1-2) it is not known whether there exists a linear algorithm for 4-coloring of planar graphs without bounded degrees. Even if there exists a linear algorithm for every degree bound d, it does not imply that one exists when degrees are unbounded. (3) might help to show (1). It is known that the d in (4) exists, since there are non-4-choosable planar graphs.
