We present an algorithm that takes as input a graph G with weights on the vertices, and
computes a maximum weight independent set S of G. If the input graph G excludes a path P …

In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showed a quasi-
polynomial-time algorithm for Maximum Weight Independent Set in Pt-free graphs, that is …

In the Maximum Independent Set problem we are asked to find a set of pairwise
nonadjacent vertices in a given graph with the maximum possible cardinality. In general …

A hole in a graph is an induced cycle of length at least 4, and an antihole is the complement
of an induced cycle of length at least 4. A hole or antihole is long if its length is at least 5. For …

We consider subexponential algorithms finding weighted homomorphisms from intersection
graphs of curves (string graphs) with n vertices to a fixed graph H. We provide a complete …

The k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k
colours for a fixed integer k such that no two adjacent vertices are coloured alike. If each …

The Colouring problem is to decide if the vertices of a graph can be coloured with at most k
colours for an integer k, such that no two adjacent vertices are coloured alike. A graph G is H …

We study the Max Partial h-Coloring problem: given a graph G, find the largest induced
subgraph of G that admits a homomorphism into H, where H is a fixed pattern graph without …

A graph is H-free if it contains no induced subgraph isomorphic to H. We prove new
complexity results for the two classical cycle transversal problems Feedback Vertex Set and …

For a graph F, a graph G is F-free if it does not contain an induced subgraph isomorphic to F.
For two graphs G and H, an H-coloring of G is a mapping f: V (G)→ V (H) such that for every …