Name
Abstract | ||
|---|---|---|
Given a graph
$$G=(V,E)$$
, an edge bipartization set of G is a subset
$$E'\subseteq E(G)$$
such that
$$G'=(V,E{\setminus } E')$$
is bipartite. An edge bipartization set that is also a matching of G is called a bipartizing matching of G. Let
$${\mathscr {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}$$
) 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$$
, the k-coloring is non-proper, also known as defective. A graph belongs to
$$\mathscr {BM}$$
if and only if it admits a (2, 1)-coloring. Lovász (1966) proved that for any integer
$$k>0$$
, any graph of maximum degree
$$\varDelta $$
admits a
$$\left( k,\lfloor \varDelta /k \rfloor \right) $$
-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}$$
, 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}}$$
. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/s10479-021-03966-9 | Annals of Operations Research |
Keywords | DocType | Volume |
Graph modification problems, Edge bipartization, Defective coloring, Planar graphs,
NP-completeness, Parameterized complexity, 05C, 90C39, 94C15 | Journal | 316 |
Issue | ISSN | Citations |
2 | 0254-5330 | 0 |
PageRank | References | Authors |
0.34 | 26 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carlos Vinícius G. C. Lima | 1 | 15 | 4.40 |
| Dieter Rautenbach | 2 | 946 | 138.87 |
| Uéverton S. Souza | 3 | 20 | 21.12 |
| Jayme Luiz Szwarcfiter | 4 | 618 | 95.79 |