Sign in
Star Coloring High Girth Planar Graphs
Journal article   Open access  Peer reviewed

Star Coloring High Girth Planar Graphs

The Electronic journal of combinatorics, Vol.15(1), pp.1-17
09/29/2008
Handle:
https://hdl.handle.net/20.500.12741/rep:8260

Abstract

A star coloring of a graph is a proper coloring such that no path on four vertices is 2-colored. We prove that every planar graph with girth at least 9 can be star colored using 5 colors, and that every planar graph with girth at least 14 can be star colored using 4 colors; the figure 4 is best possible. We give an example of a girth 7 planar graph that requires 5 colors to star color.
url
https://doi.org/10.37236/848View
Published (Version of record) Open

Metrics

5 Record Views

Details