6 papers
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…
Clique-width and induced topological minors
Paweł Rafał Bieliński, Jadwiga Czyżewska, Martin Milanič +2
A is a chordless path on four vertices. A diamond is a graph obtained from a clique of size four by removing one edge of the clique. A paw is a graph obtained from a clique o…
Dynamic data structures for twin-ordered matrices
Bartłomiej Bosek, Jadwiga Czyżewska, Evangelos Kipouridis +4
We present a dynamic data structure for representing binary matrices that are -twin-ordered, for a~fixed parameter . Our structure supports cell queries and singl…
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…
Tree-independence number VII. Excluding a star
Maria Chudnovsky, Jadwiga Czyżewska, Marcin Pilipczuk +1
We prove that for every fixed integer and every planar graph , the class of -induced-minor-free and -induced-subgraph-free graphs has polylogarithmic tree-indepe…
A note on finding long directed cycles above the minimum degree bound in 2-connected digraphs
Jadwiga Czyżewska, Marcin Pilipczuk
For a directed graph , let be the minimum among in-degrees and out-degrees of all vertices of . It is easy to see that contains a directed cycle of l…