The odd chromatic number of a toroidal graph is at most 9

作者：Tian, Fangyu; Yin, Yuxue^*

来源：INFORMATION PROCESSING LETTERS, 2023, 182: 106384.

DOI：10.1016/j.ipl.2023.106384

• Combinatorial problems
• Chromatic parameters
• NP-hard problems
• Odd coloring
• Toroidal graph

The odd coloring is a NP-hard problem in graph theory research. It is a proper coloring with an additional restriction that every non-isolated vertex has some colors that appear an odd number of times in its neighborhood. In a graph G, we use chi o(G) to represent the minimum number of colors that ensures an odd coloring. A graph G is odd k-colorable if chi o(G) < k. The above definition about odd coloring was introduced very recently by Petrusevski and Skrekovski, who also proved that if G is planar then chi o(G) < 9. A toroidal graph is a graph that can be embedded on a torus. In this paper, we study the odd chromatic number of toroidal graphs and prove that every toroidal graph G has a property that chi o (G) < 9. Since K7 is a toroidal graph, chi o (G) is no less than 7.

• 单位
  清华大学