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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02991977
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

File

Odd-subgraphs-LNCS-WG-2020.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

63

Files downloads

73