Portal de Periódicos da CAPES

A linear 5-coloring algorithm of planar graphs

1981; Academic Press; Volume: 2; Issue: 4 Linguagem: Inglês

10.1016/0196-6774(81)90031-6

1090-2678

Norishige Chiba, Takao Nishizeki, Nobuji 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.