13 citations · 77 across the 56 of their papers we have counts for
4 papers · 1 filter
Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Rank Parameters
Carla Groenland, Isja Mannens, Jesper Nederlof +2
A homomorphism from a graph to a graph is an edge-preserving mapping from to . In the graph homomorphism problem, denoted by , the graph is fixed a…
A polynomial bound on the number of minimal separators and potential maximal cliques in -free graphs of bounded clique number
Marcin Pilipczuk, Paweł Rzążewski
In this note we show a polynomial bound on the number of minimal separators and potential maximal cliques in -free graphs of bounded clique number.
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
Peter Gartland, Daniel Lokshtanov, Tomáš Masařík +3
We show that the Maximum Weight Independent Set problem (MWIS) can be solved in quasi-polynomial time on -free graphs (graphs excluding a fixed graph as an induced subgraph)…
Coloring and Recognizing Directed Interval Graphs
Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen +3
A \emph{mixed interval graph} is an interval graph that has, for every pair of intersecting intervals, either an arc (directed arbitrarily) or an (undirected) edge. We are particul…