Star coloring high girth planar graphs
type: Item
instance of: scholarly article
title: Star coloring high girth planar graphs
zbMATH Open document ID: 1165.05326
author: Craig Timmons
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/130284
full work available at URL: v15i1r124.html
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 5541029
zbMATH Keywords: star coloring
zbMATH Keywords: planar graph coloring
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5541029