Cyclic 4‐Colorings of Graphs on Surfaces |
| |
| Authors: | Atsuhiro Nakamoto Kenta Noguchi Kenta Ozeki |
| |
| Institution: | 1. GRADUATE SCHOOL OF ENVIRONMENT AND INFORMATION SCIENCES, YOKOHAMA NATIONAL UNIVERSITY, HODOGAYA‐KU, JAPAN;2. DEPARTMENT OF MATHEMATICS, KEIO UNIVERSITY, HIYOSHI, KOHOKU‐KU, JAPAN;3. NATIONAL INSTITUTE OF INFORMATICS, CHIYODA‐KU, JAPANJST, ERATO, Kawarabayashi Large Graph Project, Japan. This work was in part supported by JSPS KAKENHI Grant Number 25871053 and by Grant for Basic Science Research Projects from The Sumitomo Foundation. |
| |
| Abstract: | To attack the Four Color Problem, in 1880, Tait gave a necessary and sufficient condition for plane triangulations to have a proper 4‐vertex‐coloring: a plane triangulation G has a proper 4‐vertex‐coloring if and only if the dual of G has a proper 3‐edge‐coloring. A cyclic coloring of a map G on a surface F2 is a vertex‐coloring of G such that any two vertices x and y receive different colors if x and y are incident with a common face of G. In this article, we extend the result by Tait to two directions, that is, considering maps on a nonspherical surface and cyclic 4‐colorings. |
| |
| Keywords: | cyclic 4‐colorings 3‐edge‐colorings the Four Color Theorem |
|
|
