6
$\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$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.