On the Parameterized Complexity of Odd Coloring
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909529933873152 |
|---|---|
| author | Bhyravarapu, Sriram Kumari, Swati Reddy, I. Vinod |
| author_facet | Bhyravarapu, Sriram Kumari, Swati Reddy, I. Vinod |
| contents | A proper vertex coloring of a connected graph $G$ is called an odd coloring if, for every vertex $v$ in $G$, there exists a color that appears odd number of times in the open neighborhood of $v$. The minimum number of colors required to obtain an odd coloring of $G$ is called the \emph{odd chromatic number} of $G$, denoted by $χ_{o}(G)$. Determining $χ_o(G)$ known to be ${\sf NP}$-hard. Given a graph $G$ and an integer $k$, the \odc{} problem is to decide whether $χ_o(G)$ is at most $k$. In this paper, we study the parameterized complexity of the problem, particularly with respect to structural graph parameters. We obtain the following results: \begin{itemize}
\item We prove that the problem admits a polynomial kernel when parameterized by the distance to clique.
\item We show that the problem cannot have a polynomial kernel when parameterized by the vertex cover number unless ${\sf NP} \subseteq {\sf Co {\text -} NP/poly}$.
\item We show that the problem is fixed-parameter tractable when parameterized by distance to cluster, distance to co-cluster, or neighborhood diversity.
\item We show that the problem is ${\sf W[1]}$-hard parameterized by clique-width. \end{itemize}
Finally, we study the complexity of the problem on restricted graph classes. We show that it can be solved in polynomial time on cographs and split graphs but remains NP-complete on certain subclasses of bipartite graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_05312 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Parameterized Complexity of Odd Coloring Bhyravarapu, Sriram Kumari, Swati Reddy, I. Vinod Data Structures and Algorithms Computational Complexity A proper vertex coloring of a connected graph $G$ is called an odd coloring if, for every vertex $v$ in $G$, there exists a color that appears odd number of times in the open neighborhood of $v$. The minimum number of colors required to obtain an odd coloring of $G$ is called the \emph{odd chromatic number} of $G$, denoted by $χ_{o}(G)$. Determining $χ_o(G)$ known to be ${\sf NP}$-hard. Given a graph $G$ and an integer $k$, the \odc{} problem is to decide whether $χ_o(G)$ is at most $k$. In this paper, we study the parameterized complexity of the problem, particularly with respect to structural graph parameters. We obtain the following results: \begin{itemize} \item We prove that the problem admits a polynomial kernel when parameterized by the distance to clique. \item We show that the problem cannot have a polynomial kernel when parameterized by the vertex cover number unless ${\sf NP} \subseteq {\sf Co {\text -} NP/poly}$. \item We show that the problem is fixed-parameter tractable when parameterized by distance to cluster, distance to co-cluster, or neighborhood diversity. \item We show that the problem is ${\sf W[1]}$-hard parameterized by clique-width. \end{itemize} Finally, we study the complexity of the problem on restricted graph classes. We show that it can be solved in polynomial time on cographs and split graphs but remains NP-complete on certain subclasses of bipartite graphs. |
| title | On the Parameterized Complexity of Odd Coloring |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2503.05312 |