chapter  18
22 Pages

Nowhere-Zero Flows, List Edge Colorings

In Chapter 14, vertex colorings of graphs were introduced and in Chapter 17, edge colorings were introduced. In this chapter, colorings are described where both vertices and edges are assigned colors. The edge analogue of list colorings of vertices, introduced in Chapter 15, is also discussed in this chapter. As we saw in Chapter 17, Tait colorings are edge colorings that are intimately tied to colorings of the regions of bridgeless plane graphs. There are integer-valued labelings of the arcs of orientations of bridgeless plane graphs that also have connections to colorings of the regions of such graphs. It is this topic that is discussed first in this chapter.