Premium
On Diagonally 10‐Coloring Plane Triangulations
Author(s) -
Sanders Daniel P.,
Zhao Yue
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190200108
Subject(s) - combinatorics , diagonal , mathematics , plane (geometry) , triangulation , edge coloring , enhanced data rates for gsm evolution , colored , geometry , graph , computer science , artificial intelligence , graph power , materials science , line graph , composite material
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.