3 years ago

Eliminating Odd Cycles by Removing a Matching.

Carlos V.G.C. Lima, Jayme L. Szwarcfiter, Dieter Rautenbach, Uéverton S. Souza

We study the problem of determining whether a given graph $G=(V, E)$ admits a matching $M$ whose removal destroys all odd cycles of $G$ (or equivalently whether $G-M$ is bipartite). This problem is also equivalent to determine whether $G$ admits a $(1,1)$-coloring, which is a $2$-coloring of $V(G)$ in which each color class induces a graph of maximum degree at most $1$. We show that such a decision problem is $NP$-complete even for planar graphs of maximum degree $4$, but can be solved in linear-time in graphs of maximum degree $3$. We also present polynomial time algorithms for (claw, paw)-free graphs, graphs containing only triangles as odd cycles, graphs with bounded dominating sets, $P_5$-free graphs, and chordal graphs. In addition, we show that the problem is fixed-parameter tractable when parameterized by clique-width, which implies polynomial time solvability for many interesting graph classes of such as distance-hereditary graphs and outerplanar graphs. Finally, a $2^{vc(G)}\cdot n$ algorithm, and a kernel having at most $2\cdot nd(G)$ vertices are presented, where $vc(G)$ and $nd(G)$ are the vertex cover number and the neighborhood diversity of the input graph, respectively.

Publisher URL: http://arxiv.org/abs/1710.07741

DOI: arXiv:1710.07741v1

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.