3 papers
math.CO2026
Induced Erdős--Pósa property for long holes, long thetas, and beyond
Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk +2
The induced Erdős--Pósa property in graphs relates the maximum number of pairwise anti-adjacent copies of an object with the minimum number of neighborhoods required to hit all cop…
cs.DS2026
QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
Édouard Bonnet, Jadwiga Czyżewska, Tomáš Masařík +2
We present a quasipolynomial-time approximation scheme (QPTAS) for the Maximum Independent Set (\textsc{MWIS}) in graphs with a bounded number of pairwise vertex-disjoint and non-a…
cs.DS2026
Optimal Path Partitions in Subcubic and Almost-subcubic Graphs
Tomáš Masařík, Michał Włodarczyk, Mehmet Akif Yıldız
We consider the problem of partitioning the edges of a graph into as few paths as possible. This is a~subject of the classic conjecture of Gallai and a recurring topic in combinato…