Authors:
R. Ramamurthi, G. Sanders
Title:
Star coloring outerplanar bipartite graphs
Source:
Discussiones Mathematicae Graph Theory
Received 07.08.2014, Revised 19.12.2017, Accepted 20.12.2017, doi: 10.7151/dmgt.2109

Abstract:
A proper coloring of the vertices of a graph is called a star coloring if at least three colors are used on every 4-vertex path. We show that all outerplanar bipartite graphs can be star colored using only five colors and construct the smallest known example that requires five colors.
Keywords:

Links:
PDF