00568834

a

00568834 Sheehan, John Graph decomposition with constraints on connectivity and minimum degree. 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). 1989 New York: New York Academy of Sciences EN decomposition connectivity minimum degree spanning bipartite graph balanced spanning bipartite subgraph partition Zbl 0515.05045 Zbl 0518.05047 A classic argument due to Erd\H{o}s shows that every finite graph $G$ with minimum degree $\delta(G) \ge \delta$ contains a spanning bipartite graph $H$ with $\delta (H) \ge \vert \overline {\delta/2} \vert$. Jackson has proved that if $\delta (G) \ge \delta \ge 2$, then there exists a balanced spanning bipartite subgraph $H$ with $\delta(H) \ge 1$. {\it C. Thomassen} [J. Graph Theory 7, 165-167 (1983; Zbl 0515.05045)], developing the Erd\H{o}s argument, proved that every finite graph $G$ with $\delta (G) \ge 12k$ contains a partition $(X,Y)$ of $V(G)$ such that $\delta (X) \ge k$ and $\delta (Y) \ge k$. We discuss in this paper an, at least superficially, related question that arose from our interest [{\it R. J. Faudree} and {\it J. Sheehan}, Discrete Math. 46, 151-157 (1983; Zbl 0518.05047)] in size Ramsey numbers.