R. Ramamurthi, G. Sanders
Star coloring outerplanar bipartite graphs
Discussiones Mathematicae Graph Theory
Received 07.08.2014, Revised 19.12.2017, Accepted 20.12.2017, doi: 10.7151/dmgt.2109
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.