Abstract | ||
---|---|---|
Let β(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) such that for each F-free graph G on n vertices with minimum degree δ(G)⩾2n/(ξ(F)+2)+o(n) we have β(G)=o(n2), while there are F-free graphs H with δ(H)≥⌊2n/(ξ(F)+2)⌋ for which β(H)=Ω(n2). |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.disc.2007.06.047 | Discrete Mathematics |
Keywords | Field | DocType |
primary,secondary | Graph theory,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Bipartite graph,Extremal graph theory,Mathematics | Journal |
Volume | Issue | ISSN |
308 | 17 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tomasz Luczak | 1 | 596 | 130.60 |
Miklós Simonovits | 2 | 578 | 98.20 |