On the complexity of finding large odd induced subgraphs and odd colorings
share
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 mos(G) and χ_ odd(G), respectively. We prove that deciding whether χ_ odd(G) ≤ q is polynomial-time solvable if q ≤ 2, and NP-complete otherwise. We provide algorithms in time 2^O( rw)· n^O(1) and 2^O(q · rw)· n^O(1) to compute mos(G) and to decide whether χ_ odd(G) ≤ q on n-vertex graphs of rank-width at most 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.
READ FULL TEXT