Portal de Periódicos da CAPES

A linear algorithm for five-coloring a planar graph

1981; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-10704-5_2

1611-3349

Norishige Chiba, Takao Nishizeki, Naobumi Saito,

Graph Labeling and Dimension Problems

A simple linear algorithm is presented for coloring planar graphs with at most five colors. The algorithm employs a recursive reduction of a graph involving the deletion of a vertex of degree 6 or less possibly together with the identification of its several neighbors.