13 citations · 77 across the 56 of their papers we have counts for
4 papers · 1 filter
Subexponential-time algorithms for finding large induced sparse subgraphs
Jana Novotná, Karolina Okrasa, Michał Pilipczuk +3
Let and be hereditary graph classes. Consider the following problem: given a graph , find a largest, in terms of the number of vertices…
Representing Graphs and Hypergraphs by Touching Polygons in 3D
William Evans, Paweł Rzążewski, Noushin Saeedi +2
Contact representations of graphs have a long history. Most research has focused on problems in 2D, but 3D contact representations have also been investigated, mostly concerning fu…
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
Konrad K. Dabrowski, Carl Feghali, Matthew Johnson +3
A graph is -free if it contains no induced subgraph isomorphic to . We prove new complexity results for the two classical cycle transversal problems Feedback Vertex Set and O…
Packing Directed Cycles Quarter- and Half-Integrally
Tomáš Masařík, Irene Muzi, Marcin Pilipczuk +2
The celebrated Erdős-Pósa theorem states that every undirected graph that does not admit a family of vertex-disjoint cycles contains a feedback vertex set (a set of vertices hi…