1 citations · 2 across the 6 of their papers we have counts for
9 papers
How to Construct High Barrycades
Jakub Binięda, Michał Dębski, Grzegorz Gutowski +1
Given two positive integers height and order , the barrycade construction problem asks for a set of permutations of the integers from to such that all the proper…
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…
Words Avoiding Tangrams
Michał Dębski, Jarosław Grytczuk, Bartłomiej Pawlik +2
A \emph{tangram} is a word in which every letter occurs an even number of times. Such word can be cut into parts that can be arranged into two identical words. The minimum number o…
Strongly proper connected coloring of graphs
Michał Dębski, Jarosław Grytczuk, Paweł Naroski +1
We study a new variant of \emph{connected coloring} of graphs based on the concept of \emph{strong} edge coloring (every color class forms an \emph{induced} matching). In particula…
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…
Faster 3-coloring of small-diameter graphs
Michał Dębski, Marta Piecyk, Paweł Rzążewski
We study the 3-\textsc{Coloring} problem in graphs with small diameter. In 2013, Mertzios and Spirakis showed that for -vertex diameter-2 graphs this problem can be solved in su…
Conflict-free chromatic number vs conflict-free chromatic index
Michał Dębski, Jakub Przybyło
A vertex coloring of a given graph is conflict-free if the closed neighborhood of every vertex contains a unique color (i.e. a color appearing only once in the neighborhood). T…
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…
Strong chromatic index of sparse graphs
Michał Dębski, Jarosław Grytczuk, Małgorzata Śleszyńska-Nowak
A coloring of the edges of a graph is strong if each color class is an induced matching of . The strong chromatic index of , denoted by , is the least…