Odd cycle transversals of fullerenes (Seminar DM)

Iz MaFiRaWiki

Odd cycle transversals of fullerenes

Matej Stehlik

Torek, 6. november 2012, od 10-12, 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.

Glej tudi/See also

Seminar za diskretno matematiko

Osebna orodja