<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T14:58:58Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/1018" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/1018</identifier><datestamp>2017-03-21T19:49:26Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9928</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" lang="en" authority="83e98db8-0e77-4e2f-8669-73919c5578b2" confidence="600">Farrugia, Alastair</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2006-08-22T14:25:13Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2006-08-22T14:25:13Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en">2003</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted" lang="en">2003</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/1018</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">The study and recognition of graph families (or graph properties) is an essential part of combinatorics.   Graph colouring is another fundamental concept of graph theory that can be looked at, in large part, as the recognition of a family of graphs that are colourable according to certain rules.      
In this thesis, we study additive induced-hereditary families, and some generalisations, from a colouring perspective.   Our main results are:    
· Additive induced-hereditary families are uniquely factorisable into irreducible families.      
· If &amp;lt;i&amp;gt;P&amp;lt;/i&amp;gt; and &amp;lt;i&amp;gt;Q&amp;lt;/i&amp;gt; are additive induced-hereditary graph families, then (&amp;lt;i&amp;gt;P&amp;lt;/i&amp;gt;,&amp;lt;i&amp;gt;Q&amp;lt;/i&amp;gt;)-COLOURING is NP-hard, with the exception of GRAPH 2-COLOURING.   Moreover, with the same exception, (&amp;lt;i&amp;gt;P&amp;lt;/i&amp;gt;,&amp;lt;i&amp;gt;Q&amp;lt;/i&amp;gt;)-COLOURING is NP-complete iff &amp;lt;i&amp;gt;P&amp;lt;/i&amp;gt;- and &amp;lt;i&amp;gt;Q&amp;lt;/i&amp;gt;-RECOGNITION are both in NP.   This proves a 1997 conjecture of Kratochvíl and Schiermeyer.      
We also provide generalisations to somewhat larger families.    Other results that we prove include:    
· a characterisation of the minimal forbidden subgraphs of a hereditary property in terms of its minimal forbidden induced-subgraphs, and &amp;lt;i&amp;gt;vice versa&amp;lt;/i&amp;gt;;    
· extensions of Mihók&amp;apos;s construction of uniquely colourable graphs, and Scheinerman&amp;apos;s characterisations of compositivity, to disjoint compositive properties;    
· an induced-hereditary property has at least two factorisations into arbitrary irreducible properties, with an explicitly described set of exceptions;    
· if &amp;lt;i&amp;gt;G&amp;lt;/i&amp;gt; is a generating set for &amp;lt;i&amp;gt;A&amp;lt;/i&amp;gt; &amp;amp;#959; &amp;lt;i&amp;gt;B&amp;lt;/i&amp;gt;, where &amp;lt;i&amp;gt;A&amp;lt;/i&amp;gt; and &amp;lt;i&amp;gt;B&amp;lt;/i&amp;gt; are indiscompositive, then we can extract generating sets for &amp;lt;i&amp;gt;A&amp;lt;/i&amp;gt; and &amp;lt;i&amp;gt;B&amp;lt;/i&amp;gt; using a &amp;lt;i&amp;gt;greedy algorithm&amp;lt;/i&amp;gt;.</dim:field>
   <dim:field mdschema="dc" element="format" lang="en">application/pdf</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">738537 bytes</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="rights" lang="en">Copyright: 2003, 
  Farrugia, Alastair. All rights reserved.</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Mathematics</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">graph</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">graph property</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">vertex partition</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">graph colouring</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">hereditary</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">induced-hereditary</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">compositive</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">complexity</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">uniquely colourable graphs</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">uniquely partitionable graphs</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">unique factorisation</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Uniqueness and Complexity in Generalised Colouring</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>