13 citations · 77 across the 56 of their papers we have counts for
5 papers · 1 filter
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet +6
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Cliq…
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
Jacob Focke, Dániel Marx, Paweł Rzążewski
The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given grap…
Coloring squares of planar graphs with small maximum degree
Mateusz Krzyziński, Paweł Rzążewski, Szymon Tur
For a graph , by we denote the minimum integer , such that there is a -coloring of the vertices of in which vertices at distance at most 2 receive distinct co…
Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs
Giacomo Paesani, Daniël Paulusma, Paweł Rzążewski
We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on -free graphs, that is, graphs that do not contain some fixed graph as an induced subgra…
Faster 3-coloring of small-diameter graphs
Michał Dębski, Marta Piecyk, Paweł Rzążewski
We study the 3-\textsc{Coloring} problem in graphs with small diameter. In 2013, Mertzios and Spirakis showed that for -vertex diameter-2 graphs this problem can be solved in su…