Skip to Main content Skip to Navigation
Conference papers

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

Rémy Belmonte 1 Ignasi Sau Valls 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download
Contributor : Isabelle Gouat <>
Submitted on : Friday, November 6, 2020 - 11:09:29 AM
Last modification on : Monday, December 14, 2020 - 5:27:16 PM
Long-term archiving on: : Sunday, February 7, 2021 - 6:37:39 PM


Files produced by the author(s)




Rémy Belmonte, Ignasi Sau Valls. On the complexity of finding large odd induced subgraphs and odd colorings. 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Jun 2020, Leeds, United Kingdom. pp.67-79, ⟨10.1007/978-3-030-60440-0_6⟩. ⟨lirmm-02991977⟩



Record views


Files downloads