13 citations · 77 across the 56 of their papers we have counts for
10 papers · 1 filter
List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
Barış Can Esmer, Jacob Focke, Dániel Marx +1
The goal of this paper is to investigate a family of optimization problems arising from list homomorphisms, and to understand what the best possible algorithms are if we restrict t…
Tree decompositions with bounded independence number: beyond independent sets
Martin Milanič, Paweł Rzążewski
We continue the study of graph classes in which the treewidth can only be large due to the presence of a large clique, and, more specifically, of graph classes with bounded tree-in…
Every graph is eventually Turán-good
Natasha Morrison, JD Nir, Sergey Norin +2
Let be a graph. We show that if is large enough as a function of , then the -partite Turán graph maximizes the number of copies of among all -free graphs…
Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws
Michał Dębski, Zbigniew Lonc, Karolina Okrasa +2
For graphs and , an -coloring of is an edge-preserving mapping from to . In the -Coloring problem the graph is fixed and we ask whether an instanc…
Taming graphs with no large creatures and skinny ladders
Jakub Gajarský, Lars Jaffke, Paloma T. Lima +4
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class there exists a constant such that no member of $\mathcal{G}…
List covering of regular multigraphs with semi-edges
Jan Bok, Jiří Fiala, Nikola Jedličková +2
In line with the recent development in topological graph theory, we are considering undirected graphs that are allowed to contain {\em multiple edges}, {\em loops}, and {\em semi-e…