Min-max relations for odd cycles in planar graphs

Details Min-max relations for odd cycles in planar graphs Min-max relations for odd cycles in planar graphs

2011-08-22

arxiv.org/abs/1108.4281v1

Mathematics

Combinatorics

Scientific paper

Let m(G) be the maximum number of vertex-disjoint odd cycles of a graph G and
t(G) the minimum number of vertices whose removal makes G bipartite. We show
that t(G)<=6m(G) if G is planar. This improves the previous bound t(G)<=10m(G)
by Fiorini, Hardy, Reed and Vetta [Math. Program. Ser. B 110 (2007), 71-91].

Affiliated with

Also associated with

No associations

Rating

Min-max relations for odd cycles in planar graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Min-max relations for odd cycles in planar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Min-max relations for odd cycles in planar graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-175916