Making a K_4-free graph bipartite

Simple item page
dc.creatorSudakov, Benny
dc.date2007-06-27
dc.date.accessioned2026-07-07T08:12:49Z
dc.date.available2026-07-07T08:12:49Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/0706.4101
dc.identifierhttp://arxiv.org/abs/0706.4101
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/132589
dc.subjectCombinatorics
dc.titleMaking a K_4-free graph bipartite
dc.typetext

Files

Collections

arXiv