Matej Stehlik: Odd cycle transversals of fullerenes

Povzetek: A set of edges of a graph is an odd cycle transversal if its removal results in a bipartite graph. Determining the minimum size of an odd cycle transversal is is a classical problem, studied by numerous researchers. In this talk we will consider this problem for the class of fullerene graphs: these are plane cubic graphs with faces of size 5 and 6. Doslic and Vukicevic conjectured that every fullerene graph on n vertices has on odd cycle transversal with at most sqrt(12n/5) edges. I will show how to prove this conjecture using the theory of T-joins and T-cuts. We will deduce a number of other conjectures, including a sharp lower bound on the independence number of fullerene graphs.

This is joint work with Luerbio Faria and Sulamita Klein.