Partition of graphs with condition on the connectivity and minimum degree
Tóm tắt
C. Thomassen and M. Szegedy proved the existence of a functionf(s, t) such that the points of anyf(s, t)-connected graph have a decomposition into two non-empty sets such that the subgraphs induced by them ares-connected andt-connected, respectively. We prove, thatf(s, t) ≦ 4s+4t − 13 and examine a similar problem for the minimum degree.
Tài liệu tham khảo
C. Thomassen, Graph decomposition with constraints on the connectivity and minimum degree,J. Graph Theory, to appear.
W. Mader, Existenzn-fach zusammenhängender Teilgraphen in Graphen genügend grossen Kantendichte,Abh. Math. Sem. Hamburg Univ. 37 (1972), 86–97.
M. Szegedy, unpublished.