On the Classical and Parameterized Complexity of Strong Odd Coloring

Source abstract

A strong odd $k$-coloring of a graph $G$ is a proper $k$-coloring such that every color appearing in the neighborhood of a non-isolated vertex appears an odd number of times. The minimum $k$ for which $G$ admits a strong odd $k$-coloring is the \emph{strong odd chromatic number}, denoted by $χ_{\text{so}}(G)$, of $G$. Given a graph $G$ and an integer $k$, \textsc{strong odd $k$-colorability} problem asks whether $G$ admits a strong odd $k$-coloring. It is known that STRONG ODD $k$-COLORABILITY is NP-complete in general graphs. In this paper, we prove that the problem is NP-complete on perfect elimination bipartite graphs for $k\geq3$, which is a subclass of bipartite graphs. Furthermore, we show that $χ_{\text{so}}(G)$ is inapproximable within a factor of $O(n^{\frac{1}{2}-\varepsilon})$ for every $\varepsilon>0$. On the positive side, we obtain a linear time algorithm to compute an optimal strong odd coloring for block graphs. From a parameterized perspective, we present an FPT algorithm for STRONG ODD $k$-COLORABILITY when parameterized by treewidth. Moreover, we show that the problem cannot be solved in time $(k-\varepsilon)^{\texttt{tw}}n^{O(1)}$ for every $k\geq3$ and $\varepsilon>0$ when parameterized by treewidth under SETH. Furthermore, we show that STRONG ODD $k$-COLORABILITY does not admit a polynomial kernel when parameterized by feedback vertex set. Lastly, we prove that STRONG ODD $k$-COLORABILITY is W[1]-hard when parameterized by clique-width.