Home > News > Matej Stehlik: Odd cycle transversals of fullerenes

Matej Stehlik: Odd cycle transversals of fullerenes

Date: 4. 11. 2012
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(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.