A fast algorithm for computing bipartite edge frustration number of (3,6)-fullerenes

چکیده مقاله

The vertex and edge bipartization problems are to ¯nd the minimum number of vertices and edges, respectively, whose removal makes the graph bipartite. It is well-known that these problems are NP hard even for cubic graph. In this paper, a result is proved by which it is possible to ¯nd a fast algorithm for computing the edge bipartization number of (3,6)-fullerenes.