7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.