Star Coloring Outerplanar Bipartite Graphs

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

• chromatic number
• star coloring
• outerplanar bipartite graph
• 05c15