Deciding 4-colorability of planar triangulations is polynomial independently of the Four Color Theorem

Martin Loebl

Abstract

I will show how to express the number of proper 4-colourings of a planar triangulation as a determinant. Hence it is in particular polynomial to decide if this number is non-zero.