# Matej Stehlik: Odd cycle transversals of fullerenes

Date: 4. 11. 2012

Source: Discrete mathematics seminar

Source: Discrete mathematics seminar

Torek, 6. 11. 2012 od 10h do 12h, Plemljev seminar, Jadranska 19

**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(12

*n*/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.