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

28 octobre 21

December 13 2021. Room A707 at 13:45 (previously November 29, 2021)


Cliquez ici pour participer à la réunion

Remy Belmonte - 


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 $\Chi_{odd}(G)$, respectively. We prove that deciding whether $\Chi_ {odd}  (G) \leq q$ is polynomial-time solvable if $q \leq 2$, and NP-complete otherwise.

We provide algorithms in time $2^{O(rw)} \cdot n^{O(1)}$ and $2^{O(q \cdot rw)} \cdot n^{O(1)}$ to compute $mos(G)$ and to decide whether $\Chi_ {odd}(G) \leq 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.


Joint work with Ignasi Sau.