The <i>H</i>-Decomposition Problem for Graphs

• 作者: Teresa Sousa
• 来源期刊: 应用数学(英文)
• 学科: 数学
• 关键词: GRAPH DECOMPOSITIONS Weighted GRAPH DECOMPOSITIONS MONOCHROMATIC GRAPH DECOMPOSITIONS Turán GRAPH RAMSEY Numbers
• 年，卷（期）: yysxyw_2012,（11）
• 页码范围: 1719-1722
• 页数: 4页
• 分类号: O1

摘要

The concept of H-decompositions of graphs was first introduced by Erd?s, Goodman and Pósa in 1966, who were motivated by the problem of representing graphs by set intersections. Given graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let Ф(n,H) be the smallest number Ф, such that, any graph of order n admits an H-decomposition with at most Ф parts. The exact computation of Ф(n,H) for an arbitrary H is still an open problem. Recently, a few papers have been published about this problem. In this survey we will bring together all the results about H-decompositions. We will also introduce two new related problems, namely Weighted H-Decompositions of graphs and Monochromatic H-Decom- positions of graphs.