2 citations · 3 across the 4 of their papers we have counts for
7 papers
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…
Polynomial kernel for immersion hitting in tournaments
Łukasz Bożyk, Michał Pilipczuk
For a fixed simple digraph without isolated vertices, we consider the problem of deleting arcs from a given tournament to get a digraph which does not contain as an immersi…
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…
On the Erdős-Pósa property for immersions and topological minors in tournaments
Łukasz Bożyk, Michał Pilipczuk
We consider the Erdős-Pósa property for immersions and topological minors in tournaments. We prove that for every simple digraph , , and tournament , the fol…
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…
On the inducibility of oriented graphs on four vertices
Łukasz Bożyk, Andrzej Grzesik, Bartłomiej Kielak
We consider the problem of determining the inducibility (maximum possible asymptotic density of induced copies) of oriented graphs on four vertices. We provide exact values for mor…