2020/02/14 by Rémy Belmonte, Belmonte, Rémy, Ignasi Sau +1 · 2 citations
Computer Science · Engineering · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2002.06078
openalex publication_date 2020/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \sf mos(G) and χ\sf odd(G), respectively. We prove that deciding whether χ\sf odd(G) ≤ q is polynomial-time solvable if q ≤ 2, and NP-complete otherwise. We provide algorithms in time 2^O(\sf rw) ⋅ nO(1) and 2^O(q ⋅ \sf rw) ⋅ nO(1) to compute \sf mos(G) and to decide whether χ\sf odd(G) ≤ q on n-vertex graphs of rank-width at most \sf 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.