Making a K_4-free graph bipartite

Details Making a K_4-free graph bipartite Making a K_4-free graph bipartite

Publishing date

2007-06-27

URL

arxiv.org/abs/0706.4101v1

Science

Mathematics

Field

Combinatorics

Type

Scientific paper

Abstract

We show that every K_4-free graph G with n vertices can be made bipartite by
deleting at most n^2/9 edges. Moreover, the only extremal graph which requires
deletion of that many edges is a complete 3-partite graph with parts of size
n/3. This proves an old conjecture of P. Erdos.

Affiliated with

Also associated with

No associations

Rating

Making a K_4-free graph bipartite 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 Making a K_4-free graph bipartite, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Making a K_4-free graph bipartite will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-455875