2 citations · 3 across the 11 of their papers we have counts for
20 papers
Universally extendible characters
Benjamin Sambale
Let theta be an ordinary character or a Brauer character of a finite group N. We show that theta extends to every overgroup if and only if Z(N) <= Ker(the…
Erdős-Pósa property of tripods in directed graphs
Marcin Briański, Meike Hatzel, Karolina Okrasa +1
Let be a directed graphs with distinguished sets of sources and sinks . A tripod in is a subgraph consisting of the union of two --…
Minimal obstructions to -coloring in hereditary graph classes
Jan Goedgebeur, Jorik Jooken, Karolina Okrasa +2
For graphs and , an -coloring of is an edge-preserving mapping from to . Note that if is the triangle, then -colorings are equivalent to -color…
Tree decompositions meet induced matchings: beyond Max Weight Independent Set
Paloma T. Lima, Martin Milanič, Peter Muršič +3
For a tree decomposition of a graph , by we denote the size of a largest induced matching in all of whose edges intersect one bag of $\mathcal…
On digraphs without onion star immersions
Łukasz Bożyk, Oscar Defrain, Karolina Okrasa +1
The -onion star is the digraph obtained from a star with leaves by replacing every edge by a triple of arcs, where in triples we orient two arcs away from the center, a…
The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
Robert Ganian, Thekla Hamm, Viktoriia Korchemna +2
The generic homomorphism problem, which asks whether an input graph admits a homomorphism into a fixed target graph , has been widely studied in the literature. In this arti…
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…
Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
Konrad Majewski, Tomáš Masařík, Jana Novotná +4
We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw as an induced subgraph [Chudnovsky, Pilipczuk, Pilip…
Computing list homomorphisms in geometric intersection graphs
Sándor Kisfaludi-Bak, Karolina Okrasa, Paweł Rzążewski
A homomorphism from a graph to a graph is an edge-preserving mapping from to . Let be a fixed graph with possible loops. In the list homomorphism problem,…
Tuza's Conjecture for Threshold Graphs
Marthe Bonamy, Łukasz Bożyk, Andrzej Grzesik +4
Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds…
On objects dual to tree-cut decompositions
Łukasz Bożyk, Oscar Defrain, Karolina Okrasa +1
Tree-cut width is a graph parameter introduced by Wollan that is an analogue of treewidth for the immersion order on graphs in the following sense: the tree-cut width of a graph is…
Vertex deletion into bipartite permutation graphs
Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk +2
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines and , one on each. A bipartite permutation graph is a p…
Complexity of the list homomorphism problem in hereditary graph classes
Karolina Okrasa, Paweł Rzążewski
A homomorphism from a graph to a graph is an edge-preserving mapping from to . For a fixed graph , in the list homomorphism problem, denoted by LHom(), w…
The Complexity of Connectivity Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
Thomas Bellitto, Shaohua Li, Karolina Okrasa +2
The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is…
Sparsification Lower Bounds for List -Coloring
Hubie Chen, Bart M. P. Jansen, Karolina Okrasa +2
We investigate the List -Coloring problem, the generalization of graph coloring that asks whether an input graph admits a homomorphism to the undirected graph (possibly…
Full complexity classification of the list homomorphism problem for bounded-treewidth graphs
Karolina Okrasa, Marta Piecyk, Paweł Rzążewski
A homomorphism from a graph to a graph is an edge-preserving mapping from to . Let be a fixed graph with possible loops. In the list homomorphism problem,…
Church Synthesis on Register Automata over Linearly Ordered Data Domains
Léo Exibard, Emmanuel Filiot, Ayrat Khalimov
In a Church synthesis game, two players, Adam and Eve, alternately pick some element in a finite alphabet, for an infinite number of rounds. The game is won by Eve if the omega-wor…
Subexponential-time algorithms for finding large induced sparse subgraphs
Jana Novotná, Karolina Okrasa, Michał Pilipczuk +3
Let and be hereditary graph classes. Consider the following problem: given a graph , find a largest, in terms of the number of vertices…
Subexponential algorithms for variants of homomorphism problem in string graphs
Karolina Okrasa, Paweł Rzążewski
We consider the complexity of finding weighted homomorphisms from intersection graphs of curves (string graphs) with vertices to a fixed graph . We provide a complete dichot…
Intersecting edge distinguishing colorings of hypergraphs
Karolina Okrasa, Paweł Rzążewski
An edge labeling of a graph distinguishes neighbors by sets (multisets, resp.), if for any two adjacent vertices and the sets (multisets, resp.) of labels appearing on edge…