2 papers
cs.DS2006
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}$.
cs.DM2006
Polynomial-time algorithm for vertex k-colorability of P_5-free graphs
Marcin Kaminski, Vadim Lozin
We give the first polynomial-time algorithm for coloring vertices of P_5-free graphs with k colors. This settles an open problem and generalizes several previously known results.