Deciding 4-colorability of planar triangulations
Martin Loebl · arXiv (Cornell University) · 2015
We show, without using the Four Color Theorem, that for each planar triangulation, the number of its proper vertex colorings by 4 colors is a determinant and thus can be calculated in a polynomial time. In particular, we can efficiently decide if the number is non-zero.