Name
Abstract | ||
|---|---|---|
An additive hereditary graph property is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. If P1,…,Pn are graph properties, then a (P1,…,Pn)-decomposition of a graph G is a partition E1,…,En of E(G) such that G[Ei], the subgraph of G induced by Ei, is in Pi, for i=1,…,n. The sum of the properties P1,…,Pn is the property P1⊕⋯⊕Pn={G∈I:G has a (P1,…,Pn)-decomposition}. A property P is said to be decomposable if there exist non-trivial additive hereditary properties P1 and P2 such that P=P1⊕P2. A property is uniquely decomposable if, apart from the order of the factors, it can be written as a sum of indecomposable properties in only one way. We show that not all properties are uniquely decomposable; however, the property of k-colourable graphs Ok is a uniquely decomposable property. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.disc.2012.10.009 | Discrete Mathematics |
Keywords | Field | DocType |
Graph property,Decomposable property | Graph,Discrete mathematics,Combinatorics,Graph property,Isomorphism,Partition (number theory),Indecomposable module,Mathematics | Journal |
Volume | Issue | ISSN |
313 | 19 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Izak Broere | 1 | 143 | 31.30 |
| Michael Dorfling | 2 | 83 | 9.21 |