# On planar $4$ regular graphs

It is $$NP$$-hard to decide if a $$4$$-regular planar graph can be $$3$$-colored.

Is an exact algorithm possible that under uniform distribution is in average polynomial time?

• why the downvotes? Commented May 29, 2019 at 23:05
• @Saeed I misread "It is NP-hard" for "is it NP-hard". Now I see that the only question here is about the average case (I thought there were two questions: NP-hardness, and average case.) Commented May 31, 2019 at 13:36
• @SashoNikolov So average case is unlikely to be easy? Commented May 31, 2019 at 14:29
• I don't know. But your question is missing important details. What is the distribution on inputs: uniform on 4-regular planar graphs of a fixed size? What notion of "easy on average" do you have in mind? Should the algorithm be polytime in expectation and always output the correct answer? Should the algorithm run in polytime in the worst case and output the correct answer with high probability under the distribution? Or maybe you mean Levin's definition? Commented May 31, 2019 at 20:06
• @SashoNikolov clearer? Commented Jun 1, 2019 at 9:08