2022/06/15 by Fangyu Tian, Tian, Fangyu, Yuxue Yin +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2206.07629
openalex publication_date 2022/06/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Odd coloring is a proper coloring with an additional restriction that every non-isolated vertex has some color that appears an odd number of times in its neighborhood. The minimum number of colors k that can ensure an odd coloring of a graph G is denoted by χo(G). We say G is odd k-colorable if χo(G)≤ k. This notion is introduced very recently by Petruševski and Škrekovski, who proved that if G is planar then χo(G) ≤ 9 . A toroidal graph is a graph that can be embedded on a torus. Note that a K7 is a toroidal graph, χo(G)≤7. Tian and Yin proved that every toroidal graph is odd 9-colorable and every toroidal graph without 3-cycles is odd 9-colorable. In this paper, we proved that every toroidal graph without adjacent 3-cycles is odd 8-colorable.