𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A linear 5-coloring algorithm of planar graphs

✍ Scribed by Norishige Chiba; Takao Nishizeki; Nobuji Saito

Publisher
Elsevier Science
Year
1981
Tongue
English
Weight
526 KB
Volume
2
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

3-List-Coloring Planar Graphs of Girth 5
3-List-Coloring Planar Graphs of Girth 5
✍ C. Thomassen πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 269 KB

We prove that every planar graph of girth at least 5 is 3-choosable. It is even possible to precolor any 5-cycle in the graph. This extension implies GrΓΆtzsch's theorem that every planar graph of girth at least 4 is 3-colorable. If 1995 Academic Press, Inc.

Star coloring bipartite planar graphs
Star coloring bipartite planar graphs
✍ H. A. Kierstead; AndrΓ© KΓΌndgen; Craig Timmons πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 139 KB

## Abstract A __star coloring__ of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every bipartite planar graph can be star colored from lists of size 14, and we give an example of a bipartite planar graph that requires at least eig

Adapted list coloring of planar graphs
Adapted list coloring of planar graphs
✍ Louis Esperet; MickaΓ«l Montassier; Xuding Zhu πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 131 KB πŸ‘ 1 views

## Abstract Given an edge coloring __F__ of a graph __G__, a vertex coloring of __G__ is __adapted to F__ if no color appears at the same time on an edge and on its two endpoints. If for some integer __k__, a graph __G__ is such that given any list assignment __L__ to the vertices of __G__, with |_