Any graph with many large independent sets is almost bipartite
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
A problem on almost bipartite graphs (proposed by Erdös [1])
Suppose \(G\) has the property that for every \(m\), every subgraph on \(m\) vertices contains an independent set of size \(m/2k\). Let \(f(k)\) denote the smallest number such that \(G\) can be made bipartite by deleting \(f(k)\) vertices.Determine \(f(k)\).
In the mid 1990s, Reed proved the existence of \( f(k)\) by using graph minors, but did not publish the result. It would be of interest to improve the estimates for \( f(k)\).
Erdös, Hajnal and Szemerédi [1] proved that for every \( \epsilon>0\), there is a graph of infinite chromatic number for which every subgraph of \( m\) vertices contains an independent set of size \( (1\epsilon)m/2\). Erdös remarked that perhaps \( (1\epsilon)m/2\) could be replaced by \( m/2f(m)\) where \( f(m)\) tends to infinity arbitrarily slowly.
Bibliography  

1  P. Erdös, A. Hajnal and E. Szemerédi, On almost bipartite large
chromatic graphs, Annals of Discrete Math. 12 (1982), Theory and practice of combinatorics, NorthHolland Math. Stud., 60,
117123, NorthHolland, Amsterdam, New York, 1982.
