Title: The Maximum k-colorable Subgraph Problem
Data: 12 de julho de 2024 – 6a feira – 14h - Auditório Jacy Monteiro, Bloco B do IME
Student: Thiago Lima Oliveira

Abstract: The main topic of this Master’s thesis is the study of the maximum k-colorable subgraph problem using techniques from polyhedral theory, convex relaxations and semidefinite programming. Given a graph, one wants to find a largest induced subgraph whose vertices can be colored with k colors. In the case k = 1 the problem becomes the classical maximum stable set problem. Narasimhan introduced a polynomially computable bound for this problem which generalizes the Lovász theta function. In this dissertation we review basic results about the maximum stable set problem and its semidefinite relaxation, exhibit the bound introduced by Narasimhan, and develop novel connections based on the work of Lovász.