33 citations · 101 across the 16 of their papers we have counts for
4 papers · 1 filter
Chain minors are FPT
Jaroslaw Blasiok, Marcin Kaminski
Given two finite posets P and Q, P is a chain minor of Q if there exists a partial function f from the elements of Q to the elements of P such that for every chain in P there is a…
Beyond the Vizing's bound for at most seven colors
Marcin Kamiński, Łukasz Kowalik
Let be a simple graph of maximum degree . The edges of can be colored with at most colors by Vizing's theorem. We study lower bounds on the size of subgraphs…
Deciding k-colourability of -free graphs in polynomial time
Chính T. Hoàng, Marcin Kamiński, Vadim Lozin +2
The problem of computing the chromatic number of a -free graph is known to be NP-hard. In contrast to this negative result, we show that determining whether or not a -fre…
Max-Cut and Max-Bisection are NP-hard on unit disk graphs
Josep Diaz, Marcin Kaminski
We prove that the Max-Cut and Max-Bisection problems are NP-hard on unit disk graphs. We also show that -precision graphs are planar for > 1 / \sqrt{2}$.