# zbMATH — the first resource for mathematics

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].

##### MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C40 Connectivity 05C35 Extremal problems in graph theory