On Diagonally 10‐Coloring Plane Triangulations
Daniel P. Sanders, Yue Zhao · Journal of Graph Theory · 1995
Abstract This article shows that the vertices of a plane triangulation may be colored with 10 colors such that every pair of vertices has different colors if they are either adjacent or diagonal, that is, that they are not adjacent but are adjacent to two faces which share an edge. This improves a result of Borodin, who showed that 11 colors were sufficient. © 1996 John Wiley & Sons, Inc.