Making A K4-Free Graph Bipartite
No Thumbnail Available
Date
2014-02-17
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Addis Ababa University
Abstract
This paper presents every K4-free graph G with n vertices can be made
bipartite by deleting at most n2
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
Description
Keywords
Making A K4-Free Graph Bipartite