Star coloring high girth planar graphs (Q1010859)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Star coloring high girth planar graphs |
scientific article; zbMATH DE number 5541029
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Star coloring high girth planar graphs |
scientific article; zbMATH DE number 5541029 |
Statements
Star coloring high girth planar graphs (English)
0 references
7 April 2009
0 references
Summary: 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.
0 references
star coloring
0 references
planar graph coloring
0 references
