Article ID Journal Published Year Pages File Type
4649545 Discrete Mathematics 2008 5 Pages PDF
Abstract

Let β(G)β(G) denote the minimum number of edges to be removed from a graph G to make it bipartite. For each 3-chromatic graph F   we determine a parameter ξ(F)ξ(F) such that for each F-free graph G on n   vertices with minimum degree δ(G)⩾2n/(ξ(F)+2)+o(n)δ(G)⩾2n/(ξ(F)+2)+o(n) we have β(G)=o(n2)β(G)=o(n2), while there are F-free graphs H   with δ(H)≥⌊2n/(ξ(F)+2)⌋δ(H)≥⌊2n/(ξ(F)+2)⌋ for which β(H)=Ω(n2)β(H)=Ω(n2).

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,