Unions of bipartite graphs and graphs with bounded degree
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
Conjecture (proposed by Erdös [1])
For \(n \geq 3\), any graph with \(\binom{2n+1}{2} \binom{n}{2}1\) edges is the union of a bipartite graph and a graph with maximum degree less than \( n\).Faudree proved that every graph on \( 2n+1\) vertices having \( \binom{2n+1}{2} \binom{n}{2}1\) edges is the union of a bipartite graph and a graph with maximum degree less than \( n\). The problem remains open when the graph has more than \( 2n+1\) vertices.
Bibliography  

1 
P. Erdös, Problems and results in graph theory, The theory and
applications of graphs (Kalamazoo, MI, 1980), 331341, Wiley, New
York, 1981.
