3 papers
cs.DS2024
Odd Cycle Transversal on -free Graphs in Polynomial Time
Akanksha Agrawal, Paloma T. Lima, Daniel Lokshtanov +3
An independent set in a graph G is a set of pairwise non-adjacent vertices. A graph is bipartite if its vertex set can be partitioned into two independent sets. In the Odd Cycl…
cs.CC2023
Treewidth is NP-Complete on Cubic Graphs (and related results)
Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke +6
In this paper, we give a very simple proof that Treewidth is NP-complete; this proof also shows NP-completeness on the class of co-bipartite graphs. We then improve the result by B…
math.CO2022
On the maximum number of edges in planar graphs of bounded degree and matching number
Lars Jaffke, Paloma T. Lima
We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number.