首页 | 本学科首页   官方微博 | 高级检索  
     检索      


On packing bipartite graphs
Authors:Péter Hajnal  Márió Szegedy
Institution:(1) Bolyai Institute, University of Szeged, H-6720 Szeged, Hungary;(2) AT & T Bell Laboratories, 600 Mountain Ave., 07974 Murray Hill, HJ, U.S.A.
Abstract:G andH, two simple graphs, can be packed ifG is isomorphic to a subgraph of 
$$\overline H$$
, the complement ofH. A theorem of Catlin, Spencer and Sauer gives a sufficient condition for the existence of packing in terms of the product of the maximal degrees ofG andH. We improve this theorem for bipartite graphs. Our condition involves products of a maximum degree with an average degree. Our relaxed condition still guarantees a packing of the two bipartite graphs.the paper was written while the authors were graduate students at the University of Chicago and was completed while the first author was at M.I.T. The work of the first author was supported in part by the Air Force under Contract OSR-86-0076 and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC88-09648. The work of the second author was supported in part by NSF grant CCR-8706518.
Keywords:05 C 70
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号