On the computational complexity of the bipartizing matching problem

Carlos V. G. C. Lima (), Dieter Rautenbach (), Uéverton S. Souza () and Jayme L. Szwarcfiter ()
Additional contact information
Carlos V. G. C. Lima: Universidade Federal do Cariri
Dieter Rautenbach: Ulm University
Uéverton S. Souza: Universidade Federal Fluminense
Jayme L. Szwarcfiter: Universidade Federal do Rio de Janeiro

Annals of Operations Research, 2022, vol. 316, issue 2, No 22, 1235-1256

Abstract: Abstract Given a graph $$G=(V,E)$$ G = ( V , E ) , an edge bipartization set of G is a subset $$E'\subseteq E(G)$$ E ′ ⊆ E ( G ) such that $$G'=(V,E{\setminus } E')$$ G ′ = ( V , E \ E ′ ) is bipartite. An edge bipartization set that is also a matching of G is called a bipartizing matching of G. Let $${\mathscr {BM}}$$ BM be the family of all graphs admitting a bipartizing matching. Although every graph has an edge bipartization set, the problem of recognizing graphs G having bipartizing matchings ( $$G\in \mathscr {BM}$$ G ∈ BM ) is challenging. A (k, d)-coloring of a graph G is a k-coloring of V(G) such that each vertex of G has at most d neighbors with the same color as itself. Clearly a (k, 0)-coloring is a proper vertex k-coloring of G and, for any $$d>0$$ d > 0 , the k-coloring is non-proper, also known as defective. A graph belongs to $$\mathscr {BM}$$ BM if and only if it admits a (2, 1)-coloring. Lovász (1966) proved that for any integer $$k>0$$ k > 0 , any graph of maximum degree $$\varDelta $$ Δ admits a $$\left( k,\lfloor \varDelta /k \rfloor \right) $$ k , ⌊ Δ / k ⌋ -coloring. In this paper, we show that it is NP-complete to determine whether a 3-colorable planar graph of maximum degree 4 belongs to $$\mathscr {BM}$$ BM , i.e., (2, 1)-colorable. Besides, we show that it is NP-complete to determine whether planar graphs of maximum degree 6 or 8 admit a (2, 2) or (2, 3)-coloring, respectively. Due to Lovász (1966), our results are tight in the sense that on graphs with maximum degree three, five, and seven, there always exists a (2, 1), (2, 2), and (2, 3)-coloring, respectively. Finally, we present polynomial-time algorithms for particular graph classes, besides some remarks on the parameterized complexity of the problem of recognizing graphs in $${\mathscr {BM}}$$ BM .

Keywords: Graph modification problems; Edge bipartization; Defective coloring; Planar graphs; NP-completeness; Parameterized complexity; 05C; 90C39; 94C15 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-021-03966-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:316:y:2022:i:2:d:10.1007_s10479-021-03966-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-021-03966-9

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().