A survey on the cyclic coloring and its relaxations (Q2214302)

A planar graph \(G\) can have more different planar embeddings called also plane drawings of \(G\). Every plane drawing is called a plane graph. Edges of a plane graph separate the plane into regions called faces. A coloring \(c:V(G)\rightarrow\{1,\dots,k\}\) of a plane graph \(G\) is called cyclic if \(c(u)\neq c(v)\) for every two vertices \(u\) and \(v\) that belong to a common face. The minimum \(k\) for which there exists a cyclic coloring of a plane graph \(G\) is called the cyclic chromatic number of \(G\) and is denoted by \(\chi_c(G)\). This work bring an exhaustive overview of upper bounds on \(\chi_c(G)\) in the first part. Later, several relaxations are treated. In particular, facial rainbow colorings, \(\ell\)-facial colorings, odd colorings, unique-maximum colorings, cyclic edge colorings, facial rainbow edge colorings, \(\ell\)-facial edge colorings, odd edge colorings and unique-maximum edge colorings are presented together with several results about their chromatic numbers.