1 citations · 2 across the 4 of their papers we have counts for
5 papers
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…
Burling graphs in graphs with large chromatic number
Tara Abrishami, Marcin Briański, James Davies +4
A graph class is -bounded if the only way to force large chromatic number in graphs from the class is by forming a large clique. In the 1970s, Erdős conjectured that intersectio…
Tabular intermediate logics comparison
Paweł Rzążewski, Michał Stronkowski
Tabular intermediate logics are intermediate logics characterized by finite posets treated as Kripke frames. For a poset , let denote the corresponding…
An -Approximation Algorithm for Vertex Cover on String Graphs
Édouard Bonnet, Paweł Rzążewski
We present a 1.8334-approximation algorithm for Vertex Cover on string graphs given with a representation, which takes polynomial time in the size of the representation; the exact…
Polynomial-time recognition and maximum independent set in Burling graphs
Paweł Rzążewski, Bartosz Walczak
A Burling graph is an induced subgraph of some graph in Burling's construction of triangle-free high-chromatic graphs. Equivalently, a Burling graph is a graph that admits a so-cal…