An odd coloring of a graph G is a proper coloring such that for every non-isolated vertex, at least one color must appear an odd number of times in the open neighborhood of v. The minimum number of colors needed in an odd coloring of a graph G is called odd chromatic number, denoted by \(\chi _o(G)\) . Given a graph G and a positive integer k, the Odd coloring problem is to check whether \(\chi _o(G) \le k\) . It is known that Odd coloring is NP-complete even on bipartite graphs.