An Odd Cycle Transversal is a set of vertices that, when removed from a graph, renders it bipartite.
does the collection of "critical" sets of vertices, whose removal renders a graph bipartite, resemble a Matroid, i.e. will a greedy strategy yield a critical vertex set of minimal cardinality?
I am looking for a proof deciding the matroid property that either affirm the success of the greedy strategy or for a proof of at least the existence of instances, where the greedy strategy doesn't yield a minimal set of vertices whose removal renders the graph bipartite; a concrete counter example would be more than I dare to hope for in that case.
By a critical set of vertices, in this context, I mean a set of vertices whose removal renders a graph bipartite, but none of its proper subsets has that property.
By the greedy strategy I mean repeatedly removing a vertex that is on a maximal number of odd cycles in the graph resulting from previous greedy vertex deletions.
Please note that the question is not as to whether it is efficiently possible to determine the number of odd cycles on which a vertex; it is rather assumed that that information comes from a kind of oracle or whatever celestial being you prefer.