On the complexity of finding large odd induced subgraphs and odd colorings

Abstract

We study the complexity of the problems of finding, given a graph $G$, a largest induced subgraph of $G$ with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition $V(G)$. We call these parameters $\mathsf{mos}(G)$ and ${\chi }_{\mathsf{odd}}(G)$, respectively. We prove that deciding whether ${\chi }_{\mathsf{odd}}(G)\le q$ is polynomial-time solvable if $q\le 2$, and NP-complete otherwise. We provide algorithms in time $2^{O(\mathsf{rw})}\cdot n^{O(1)}$ and $2^{O(q\cdot \mathsf{rw})}\cdot n^{O(1)}$ to compute $\mathsf{mos}(G)$ and to decide whether ${\chi }_{\mathsf{odd}}(G)\le q$ on $n$-vertex graphs of rank-width at most $\mathsf{rw}$, respectively, and we prove that the dependency on rank-width is asymptotically optimal under the ETH. Finally, we give some tight bounds for these parameters on restricted graph classes or in relation to other parameters.

arXiv comment24 pages, 8 figures