19 citations · 37 across the 14 of their papers we have counts for
Showing 2012Show all
3 papers · 1 filter
cs.DS2012
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…
cs.DS2012★ 3 cited
Nonblocker in H-minor free graphs: kernelization meets discharging
Lukasz Kowalik
Perhaps the best known kernelization result is the kernel of size 335k for the Planar Dominating Set problem by Alber et al. [JACM 2004], later improved to 67k by Chen et al. [SICO…
cs.DS2012★ 1 cited
A 9k kernel for nonseparating independent set in planar graphs
Lukasz Kowalik, Marcin Mucha
We study kernelization (a kind of efficient preprocessing) for NP-hard problems on planar graphs. Our main result is a kernel of size at most 9k vertices for the Planar Maximum Non…