Some results on decomposable and reducible graph properties

详细信息	查看全文 | 推荐本文 |

• 作者：Michael J. Dorfling ^{michaeljd@telkomsa.net}
• 关键词：Graph property ; Factorization ; Decomposability ; Additive ; Hereditary
• 刊名：Discrete Mathematics
• 出版年：2012
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：28 August, 2012
• 卷：312
• 期：16
• 页码：2491-2497
• 文件大小：226 K

摘要

A property of graphs is a non-empty isomorphism-closed class of simple graphs. If are properties of graphs, the property is the class of all graphs that have a vertex partition such that for . The property is the class of all graphs that have an edge partition such that for . A property which is not the class of all graphs is said to be reducible over a set of properties if there exist properties such that . is decomposable over if . We study questions of the form: If is reducible (decomposable) over , does it follow that is reducibe (decomposable) over ?