H-packing of k-chromatic graphs
H-packing of k-chromatic graphs
复制标题
k 色图的 H 堆积
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
R. Yuster
中科院分区：
文献类型：
--
作者：
R. Yuster
对于图H和G，设pH（G）表示G中H的一组边不相交的副本所覆盖的最大边数.证明了若H是k色的，则pH（G）> > pKk（G）o V（G）2 .误差项不能得到很大的改进，因为对于任意的p> 0，存在p（H）= k的图H使得对于任意的n足够大，存在n阶图G使得p H（G）6 pKk（G）n 2 p。我们给出了这个结果在极值图中的几个应用
For graphs H and G, let pH(G) denote the maximum number of edges covered by a set of edge-disjoint copies of H in G. We prove that if H is k-chromatic, then pH(G) > > pKk (G) o V(G) 2 . The error term cannot be improved much, as for any � > 0 there are graphs H with � (H) = k such that for all n sufciently large, there are graphs G with n vertices for which pH(G) 6 pKk (G) n 2 � . We present several applications of this result in extremal graph