Abstract

Three Open Problems in Graph Theory

Vadim Lozin
Mon Apr. 12 at 1:10pm in the Graduate Student Lounge

This talk is devoted to three open problems in graph theory. We first review available information related to the problems, then propose a conjecture for each of them, and finally, exhibit some results verifying the conjectures. Two of the problems are of combinatorial nature, while the third one deals with determination of complexity status of algorithmic problems between 2- and 3-colorability. The recognition of 3-colorable graphs is known to be an NP-complete problem, while 2-colorable (i.e. bipartite) graphs can be recognized in polynomial time. To make the complexity gap more precise, we study intermediate graph classes between these two extremes. The conjecture associated with this problem characterizes the boundary that separates "simple" and "hard" instances.