{"id":"arxiv/2610.01441","url":"https://arxiv.org/abs/2610.01441","tags":["cs.DM","math.CO"],"score":0,"title":"On the Classical and Parameterized Complexity of Strong Odd Coloring","domain":"cs.DM","source":"arxiv","authors":["Dinabandhu Pradhan","Vaishali Sharma","Shaily Verma"],"reviews":0,"subject":"cs.DM","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-01","reactions":{}}