search

Speaker - Bartosz Walczak

Coloring and Maximum Weight Independent Set of rectangles Wed, Nov 6, 2019 12:30 CET

Speakers: Bartosz Walczak

We prove that every intersection graph of axis-parallel rectangles in the plane with clique number ω has chromatic number O(ω log ω), which is the first improvement of the original O(ω²) bound of Asplund and Grünbaum from 1960. As a consequence, we obtain a polynomial-time O(log log n)-approximation algorithm for Maximum Weight Independent Set in axis-parallel rectangles, improving the previous best approximation ratio of O(log n/log log n). Joint work with Parinya Chalermsook.

Sparse Kneser graphs are hamiltonian Wed, Aug 29, 2018 12:30 CEST

Speakers: Bartosz Walczak