Sheehan, John Graph decomposition with constraints on connectivity and minimum degree. (English) Zbl 0792.05113 Capobianco, Michael F. (ed.) et al., Graph theory and its applications: East and West. Proceedings of the first China-USA international conference, held in Jinan, China, June 9-20, 1986. New York: New York Academy of Sciences,. Ann. N. Y. Acad. Sci. 576, 480-486 (1989). A classic argument due to Erdős shows that every finite graph \(G\) with minimum degree \(\delta(G) \geq \delta\) contains a spanning bipartite graph \(H\) with \(\delta (H) \geq | \overline {\delta/2} |\). Jackson has proved that if \(\delta (G) \geq \delta \geq 2\), then there exists a balanced spanning bipartite subgraph \(H\) with \(\delta(H) \geq 1\). C. Thomassen [J. Graph Theory 7, 165-167 (1983; Zbl 0515.05045)], developing the Erdős argument, proved that every finite graph \(G\) with \(\delta (G) \geq 12k\) contains a partition \((X,Y)\) of \(V(G)\) such that \(\delta (X) \geq k\) and \(\delta (Y) \geq k\). We discuss in this paper an, at least superficially, related question that arose from our interest [R. J. Faudree and J. Sheehan, Discrete Math. 46, 151-157 (1983; Zbl 0518.05047)] in size Ramsey numbers.For the entire collection see [Zbl 0788.00046]. Cited in 1 Document MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C40 Connectivity 05C35 Extremal problems in graph theory Keywords:decomposition; connectivity; minimum degree; spanning bipartite graph; balanced spanning bipartite subgraph; partition Citations:Zbl 0515.05045; Zbl 0518.05047 PDFBibTeX XMLCite \textit{J. Sheehan}, in: Graph theory and its applications: East and West. Proceedings of the first China-USA international conference, held in Jinan, China, June 9--20, 1986. New York: New York Academy of Sciences. 480--486 (1989; Zbl 0792.05113)