Editing Outerplanar graph (section)

===Coloring===
All loopless outerplanar graphs can be [[graph coloring|colored]] using only three colors;<ref name="ps86">{{harvtxt|Proskurowski|Sysło|1986}}.</ref> this fact features prominently in the simplified proof of [[Václav Chvátal|Chvátal's]] [[art gallery theorem]] by {{harvtxt|Fisk|1978}}. A 3-coloring may be found in [[linear time]] by a [[greedy coloring]] algorithm that removes any vertex of [[degree (graph theory)|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 (graph theory)|degree]] of any vertex of the graph or one plus the maximum degree. However, in a connected outerplanar graph, the chromatic index is equal to the maximum degree except when the graph forms a [[cycle (graph theory)|cycle]] of odd length.<ref>{{harvtxt|Fiorini|1975}}.</ref> An edge coloring with an optimal number of colors can be found in linear time based on a [[breadth first search|breadth-first traversal]] of the weak dual tree.<ref name="ps86"/>