Abstract for talk by Vadim Lozin

Title: Cliques, Coloring and Satisfiability: from structure to algorithms
 
Cliques, coloring and satisfiability are three central problems of theoretical computer science each of which is generally NP-hard. On the other hand, each of them may become tractable when restricted to instances of particular structure. In this talk we analyze how the structure of the input can affect the computational complexity of these problems. We also discuss some algorithmic tools to solve the problems with a focus given to transformations of graphs and of CNF formulas.