On the Classical and Parameterized Complexity of Strong Odd Coloring
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 χ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≥3, which is a subclass of bipartite graphs. Furthermore, we show that χso(G) is inapproximable within a factor of O(n1/2−ε) for every ε>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−ε)twnO(1) for every k≥3 and ε>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.
Related
- From b-Coloring to b*-Coloring: Large Girth and Parameterized Complexity
- Strong edge coloring of graphs with maximum degree $6$
- Strong coloring numbers of grids
- Computational complexity of the H-coloring problem in cubic graphs
- Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
BibTeX
@misc{pradhan2026classical,
title = {{On the Classical and Parameterized Complexity of Strong Odd Coloring}},
author = {Dinabandhu Pradhan and Vaishali Sharma and Shaily Verma},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01441},
eprint = {2610.01441},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01441},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - On the Classical and Parameterized Complexity of Strong Odd Coloring
AU - Dinabandhu Pradhan
AU - Vaishali Sharma
AU - Shaily Verma
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01441
UR - https://arxiv.org/abs/2610.01441
AB - 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 χ_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≥3, which is a subclass of bipartite graphs. Furthermore, we show that χ_so(G) is inapproximable within a factor of O(n^1/2−ε) for every ε>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−ε)^twn^O(1) for every k≥3 and ε>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.
ER -