research
∙
07/14/2023
Sparse induced subgraphs in P_6-free graphs
We prove that a number of computational problems that ask for the larges...
share
research
∙
01/30/2023
Cops and robbers on P_5-free graphs
We prove that every connected P_5-free graph has cop number at most two,...
research
∙
07/12/2021
Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws
For graphs G and H, we say that G is H-free if it does not contain H as ...
research
∙
06/04/2020
List-three-coloring P_t-free graphs with no induced 1-subdivision of K_1,s
Let s and t be positive integers. We use P_t to denote the path with t v...
research
∙
05/04/2020
Complexity of C_k-coloring in hereditary classes of graphs
For a graph F, a graph G is F-free if it does not contain an induced sub...
research
∙
04/20/2020
Finding large H-colorable subgraphs in hereditary graph classes
We study the Max Partial H-Coloring problem: given a graph G, find the l...
research
∙
03/11/2020
Induced subgraphs of bounded treewidth and the container method
A hole in a graph is an induced cycle of length at least 4. A hole is lo...
research
∙
12/24/2019
Maximum independent sets in (pyramid, even hole)-free graphs
A hole in a graph is an induced cycle with at least 4 vertices. A graph ...
research
∙
07/28/2019
Avoidable Vertices and Edges in Graphs
A vertex in a graph is simplicial if its neighborhood forms a clique. We...
research
∙
07/10/2019
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
In the Maximum Independent Set problem we are asked to find a set of pai...
research
∙
03/12/2019
On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five
A hole in a graph is an induced cycle of length at least 4, and an antih...
research
∙
02/07/2018
Four-coloring P_6-free graphs. II. Finding an excellent precoloring
This is the second paper in a series of two. The goal of the series is t...
research
∙
02/07/2018