×

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
PDFBibTeX XMLCite