Strong odd coloring problem remains hard on special graph classes
On the Classical and Parameterized Complexity of Strong Odd Coloring
Discrete Mathematics
Summary
This paper studies a special way of coloring networks where each color near a connection appears an odd number of times. The researchers show that deciding this kind of coloring is difficult even for certain simple network types. They also provide fast methods for some networks and analyze how the problem complexity changes with different parameters. Their work proves limits on how well these problems can be approximated or simplified.
What this means in practice
- •For graph algorithm designers: Understand which graph classes allow efficient strong odd coloring algorithms and which remain computationally hard.
- •For network security teams: Recognize limitations on simplifying certain network coloring problems that could represent conflict or resource constraints.
A theory result. No direct application yet.
Authors
Dinabandhu Pradhan, Vaishali Sharma, Shaily Verma
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.