A Survey on the Cyclic Coloring and its Relaxations

Abstract

A cyclic coloring of a plane graph is a vertex coloring such that any two vertices incident with the same face receive distinct colors. This type of coloring was introduced more than fifty years ago, and a lot of research in chromatic graph theory was sparked by it. This paper is a survey on the state of the art concerning the cyclic coloring and relaxations of this graph invariant.

Keywords

• plane graph
• edge coloring
• vertex coloring
• 05c15
• 05c10