Outerplanar Graph - Coloring

Coloring

All loopless outerplanar graphs can be colored using only three colors; this fact features prominently in the simplified proof of Chvátal's art gallery theorem by Fisk (1978). A 3-coloring may be found in linear time by a greedy coloring algorithm that removes any vertex of degree at most two, colors the remaining graph recursively, and then adds back the removed vertex with a color different from the colors of its two neighbors.

According to Vizing's theorem, the chromatic index of any graph (the minimum number of colors needed to color its edges so that no two adjacent edges have the same color) is either the maximum degree of any vertex of the graph or one plus the maximum degree. However, in an outerplanar graph, the chromatic index is equal to the maximum degree except when the graph forms a cycle of odd length. An edge coloring with an optimal number of colors can be found in linear time based on a breadth-first traversal of the weak dual tree.