13 citations · 77 across the 56 of their papers we have counts for
16 papers · 1 filter
Clique-width and induced topological minors
Paweł Rafał Bieliński, Jadwiga Czyżewska, Martin Milanič +2
A is a chordless path on four vertices. A diamond is a graph obtained from a clique of size four by removing one edge of the clique. A paw is a graph obtained from a clique o…
Induced matching treewidth and tree-independence number, revisited
Noga Alon, Martin Milanič, Paweł Rzążewski
We study two graph parameters defined via tree decompositions: tree-independence number and induced matching treewidth. Both parameters are defined similarly as treewidth, but with…
On Approximate MMS Allocations on Restricted Graph Classes
Václav Blažej, Michał Dębski, Zbigniew Lonc +2
We study the problem of fair division of a set of indivisible goods with connectivity constraints. Specifically, we assume that the goods are represented as vertices of a connected…
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.
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…
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…
Clique-Width: Harnessing the Power of Atoms
Konrad K. Dabrowski, Tomáš Masařík, Jana Novotná +2
Many NP-complete graph problems are polynomial-time solvable on graph classes of bounded clique-width. Several of these problems are polynomial-time solvable on a hereditary graph…
Packing Directed Cycles Quarter- and Half-Integrally
Tomáš Masařík, Irene Muzi, Marcin Pilipczuk +2
The celebrated Erdős-Pósa theorem states that every undirected graph that does not admit a family of vertex-disjoint cycles contains a feedback vertex set (a set of vertices hi…
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…
On edge intersection graphs of paths with 2 bends
Martin Pergel, Paweł Rzążewski
An EPG-representation of a graph is a collection of paths in a plane square grid, each corresponding to a single vertex of , so that two vertices are adjacent if and only if…
Sequences of radius for complete bipartite graphs
Michał Dębski, Zbigniew Lonc, Paweł Rzążewski
A \emph{-radius sequence} for a graph is a sequence of vertices of (typically with repetitions) such that for every edge of vertices and appear at least…
Fixing improper colorings of graphs
Valentin Garnero, Konstanty Junosza-Szaniawski, Mathieu Liedloff +2
In this paper we consider a variation of a recoloring problem, called the Color-Fixing. Let us have some non-proper -coloring of a graph . We investigate the problem of f…
Homothetic Polygons and Beyond: Intersection Graphs, Recognition, and Maximum Clique
Valentin E. Brimkov, Konstanty Junosza-Szaniawski, Sean Kafer +5
We study the {\sc Clique} problem in classes of intersection graphs of convex sets in the plane. The problem is known to be NP-complete in convex-set intersection graphs and straig…
An Exact Algorithm for the Generalized List -Coloring Problem
Konstanty Junosza-Szaniawski, Paweł Rzążewski
The generalized list -coloring is a common generalization of many graph coloring models, including classical coloring, -labeling, channel assignment and -coloring. Ev…
Determining L(2,1)-Span in Polynomial Space
Konstanty Junosza-Szaniawski, Paweł Rzą\zewski
A -L(2,1)-labeling of a graph is a function from its vertex set into the set , such that the labels assigned to adjacent vertices differ by at least 2, and labels a…