The property of k-colourable graphs is uniquely decomposable
| dc.contributor.author | Broere, Izak | |
| dc.contributor.author | Dorfling, Michael J. | |
| dc.contributor.email | izak.broere@up.ac.za | en_US |
| dc.date.accessioned | 2013-04-16T11:12:10Z | |
| dc.date.available | 2013-04-16T11:12:10Z | |
| dc.date.issued | 2013-10 | |
| dc.description.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 = fG 2 I : G has a (P1; : : : ;Pn)-decompositiong. 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. Keywords: graph property, decomposable property | en_US |
| dc.description.librarian | hb2013 | en_US |
| dc.description.uri | http://www.elsevier.com/locate/disc | en_US |
| dc.identifier.citation | Broere, I & Dorfling, MJ 2013, 'The property of k-colourable graphs is uniquely decomposable', Discrete Mathematics, vol. 313, no. 19, pp. 1961-1964. | en_US |
| dc.identifier.issn | 0012-365X (print) | |
| dc.identifier.issn | 1872-681X (online) | |
| dc.identifier.other | 10.1016/j.disc.2012.10.009 | |
| dc.identifier.uri | http://hdl.handle.net/2263/21287 | |
| dc.language.iso | en | en_US |
| dc.publisher | Elsevier | en_US |
| dc.rights | © 2012 Elsevier Ltd. All rights reserved. Notice : this is the author’s version of a work that was accepted for publication in Discrete Mathematics. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Discrete Mathematics, NYP. | en_US |
| dc.subject | Graph property | en_US |
| dc.subject | Decomposable property | en_US |
| dc.title | The property of k-colourable graphs is uniquely decomposable | en_US |
| dc.type | Postprint Article | en_US |