3 papers
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…
math.CO2025
On the Uncrossed Number of Graphs
Martin Balko, Petr HlinÄný, Tomáš MasaÅÃk +3
Visualizing a graph in the plane nicely, for example, without crossings, is unfortunately not always possible. To address this problem, MasaÅÃk and HlinÄný [GD 2023] recent…