Colorings of plane graphs: a survey. (English) Zbl 1259.05042

Borodin, O. V.

Discrete Math. 313, No. 4, 517-539 (2013).

Summary: After a brief historical account, a few simple structural theorems about plane graphs useful for coloring are stated, and two simple applications of discharging are given. Afterwards, the following types of proper colorings of plane graphs are discussed, both in their classical and choosability (list coloring) versions: simultaneous colorings of vertices, edges, and faces (in all possible combinations, including total coloring), edge-coloring, cyclic coloring (all vertices in any small face have different colors), 3-coloring, acyclic coloring (no 2-colored cycles), oriented coloring (homomorphism of directed graphs to small tournaments), a special case of circular coloring (the colors are points of a small cycle, and the colors of any two adjacent vertices must be nearly opposite on this cycle), 2-distance coloring (no 2-colored paths on three vertices), and star coloring (no 2-colored paths on four vertices). The only improper coloring discussed is injective coloring (any two vertices having a common neighbor should have distinct colors).

MSC:

05C10	Planar graphs; geometric and topological aspects of graph theory
05C15	Coloring of graphs and hypergraphs
05-02	Research exposition (monographs, survey articles) pertaining to combinatorics

Keywords:

plane graph; planar graph; coloring; list coloring