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


Rainbow number of matchings in planar graphs
Authors:Zemin Jin  Kun Ye
Affiliation:Department of Mathematics, Zhejiang Normal University Jinhua, 321004, PR China
Abstract:The rainbow numberrb(G,H) for the graph H in G is defined to be the minimum integer c such that any c-edge-coloring of G contains a rainbow H. As one of the most important structures in graphs, the rainbow number of matchings has drawn much attention and has been extensively studied. Jendrol et al. initiated the rainbow number of matchings in planar graphs and they obtained bounds for the rainbow number of the matching kK2 in the plane triangulations, where the gap between the lower and upper bounds is O(k3). In this paper, we show that the rainbow number of the matching kK2 in maximal outerplanar graphs of order n is n+O(k). Using this technique, we show that the rainbow number of the matching kK2 in some subfamilies of plane triangulations of order n is 2n+O(k). The gaps between our lower and upper bounds are only O(k).
Keywords:Rainbow number  Rainbow matching  Planar graph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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