Exécution de notre outil de synthèse sur un nouvel article

Vérifiez l’article ci-dessous, puis lancez sa synthèse.

Deciding 4-colorability of planar triangulations

Martin Loebl

Résumé : 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.

Soumis à arXiv le 15 Mai. 2015