
Tuza's Conjecture for Threshold Graphs
Tuza famously conjectured in 1981 that in a graph without k+1 edgedisjo...
read it

On objects dual to treecut decompositions
Treecut width is a graph parameter introduced by Wollan that is an anal...
read it

Vertex deletion into bipartite permutation graphs
A permutation graph can be defined as an intersection graph of segments ...
read it

Complexity of the list homomorphism problem in hereditary graph classes
A homomorphism from a graph G to a graph H is an edgepreserving mapping...
read it

The Complexity of Connectivity Problems in ForbiddenTransition Graphs and EdgeColored Graphs
The notion of forbiddentransition graphs allows for a robust generaliza...
read it

Sparsification Lower Bounds for List HColoring
We investigate the List HColoring problem, the generalization of graph ...
read it

Full complexity classification of the list homomorphism problem for boundedtreewidth graphs
A homomorphism from a graph G to a graph H is an edgepreserving mapping...
read it

Subexponentialtime algorithms for finding large induced sparse subgraphs
Let C and D be hereditary graph classes. Consider the following problem:...
read it

Finegrained complexity of graph homomorphism problem for boundedtreewidth graphs
For graphs G and H, a homomorphism from G to H is an edgepreserving map...
read it

Subexponential algorithms for variants of homomorphism problem in string graphs
We consider the complexity of finding weighted homomorphisms from inters...
read it

Intersecting edge distinguishing colorings of hypergraphs
An edge labeling of a graph distinguishes neighbors by sets (multisets, ...
read it
Karolina Okrasa
is this you? claim profile