LIMA, Carlos Vinicius Gomes Costa. Sobre b-coloração de grafos com cintura pelo menos 6. 2013. 60 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T12:13:18Z No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-14T15:33:44Z (GMT) No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) / Made available in DSpace on 2016-07-14T15:33:44Z (GMT). No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) Previous issue date: 2013 / The coloring problem is among the most studied in the Graph Theory due to its great theoretical and practical importance. Since the problem of coloring the vertices of a graph G either with the smallest amount of colors is NP-hard, various coloring heuristics are examined to obtain a proper colouring with a reasonably small number of colors. Given a graph G, the b heuristic of colouring comes down to decrease the amount of colors in a proper colouring c, so that, if all vertices of a color class fail to see any color in your neighborhood, then we can change the color to any color these vertices nonexistent in your neighborhood. Thus, we obtain a coloring c ′ with a color unless c. Irving and Molove defined the b-coloring of a graph G as a coloring where every color class has a vertex that is adjacent the other color classes. These vertices are called b-vertices. Irving and Molove also defined the b-chromatic number as the largest integer k, such that G admits a b-coloring by k colors. They showed that determine the value of the b-chromatic number of any graph is NP-hard, but polynomial for trees. Irving and Molove also defined the m-degree of a graph, which is the largest integer m(G) such that there are m(G) vertices with degree at least m(G) − 1. Irving and Molove showed that the m-degree is an upper limit to the b-chromatic number and showed that it is m(T) or m(T)−1 to every tree T, where its value is m(T) if, and only if, T has a good set. In this dissertation, we analyze the relationship between the girth, which is the size of the smallest cycle, and the b-chromatic number of a graph G. More specifically, we try to find the smallest integer g ∗ such that if the girth of G is at least g ∗ , then the b-chromatic number equals m(G) or m(G)−1. Show that the value of g ∗ is at most 6 could be an important step in demonstrating the famous conjecture of Erd˝os-Faber-Lov´asz, but the best known upper limit to g ∗ is 9. We characterize the graphs whose girth is at least 6 and not have a good set and show how b-color them optimally. Furthermore, we show how b-color, also optimally, graphs whose girth is at least 7 and not have good set. / O problema de coloração está entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importância teorica e prática. Dado que o problema de colorir os vértices de um grafo G qualquer com a menor quantidade de cores é NP-difícil, várias heurísticas de coloração são estudadas a fim de obter uma coloração própria com um número de cores razoavelmente pequeno. Dado um grafo G, a heurística b de coloração se resume a diminuir a quantidade de cores utilizadas em uma coloração própria c, de modo que, se todos os vértices de uma classe de cor deixam de ver alguma cor em sua vizinhança, então podemos modificar a cor desses vértices para qualquer cor inexistente em sua vizinhança. Dessa forma, obtemos uma coloração c′ com uma cor a menos que c. Irving e Molove definiram a b-coloração de um grafo G como uma coloração onde toda classe de cor possui um vértice que é adjacente as demais classes de cor. Esses vértices são chamados b-vértices. Irving e Molove também definiram o número b-cromático como o maior inteiro k tal que G admite uma b-coloração por k cores. Eles mostraram que determinar o número b-cromático de um grafo qualquer é um problema NP-difícil, mas polinomial para árvores. Irving e Molove também definiram o m-grau de um grafo, que é o maior inteiro m(G) tal que existem m(G) vértices com grau pelo menos m(G)−1. Irving e Molove mostraram que o m-grau é um limite superior para número b-cromático e mostraram que o mesmo é igual a m(T) ou a m(T)−1, para toda árvore T, onde o número b-cromático é igual a m(T) se, e somente se, T possui um conjunto bom. Nesta dissertação, verificamos a relação entre a cintura, que é o tamanho do menor ciclo, e o número b-cromático de um grafo G. Mais especificamente, tentamos encontrar o menor inteiro g∗ tal que, se a cintura de G é pelo menos g∗, então o número b-cromático é igual a m(G) ou m(G)−1. Mostrar que o valor de g∗ é no máximo 6 poderia ser um passo importante para demonstrar a famosa Conjectura de Erdós-Faber-Lovasz, mas o melhor limite superior conhecido para g∗ é 9. Caracterizamos os grafos cuja cintura é pelo menos 6 e não possuem um conjunto bom e mostramos como b-colori-los de forma ótima. Além disso, mostramos como bicolorir, também de forma ótima, os grafos cuja cintura é pelo menos 7 e não possuem conjunto bom.

Dans cette thèse, nous étudions des problèmes d'identification des sommets dans les graphes. Identifier les sommets d'un graphe consiste à attribuer à chaque sommet un objet qui rend le sommet unique par rapport aux autres. Nous nous intéressons particulièrement aux codes identifiants : sous-ensembles de sommets d'un graphe, dominants, tels que le voisinage fermé de chaque sommet du graphe a une intersection unique avec l'ensemble. Les sommets du code identifiant peuvent être considérés comme des capteurs et chaque sommet du graphe comme un lieu possible pour une défaillance. Nous caractérisons tout d'abord l'ensemble des graphes pour lesquels tous les sommets sauf un sont nécessaires dans tout code identifiant. Le problème consistant à trouver un code identifiant optimal, c'est-`a-dire de taille minimale, étant NP-difficile, nous l'étudions sur quatre classes restreintes de graphes. Suivant les cas, nous pouvons résoudre complètement le problème (pour les graphes de Sierpinski), améliorer les bornes générales (pour les graphes d'intervalles, les graphes adjoints, la grille du roi) ou montrer que le problème reste difficile même restreint (pour les graphes adjoints). Nous considérons ensuite des variations autour des codes identifiants permettant plus de flexibilité pour les capteurs. Nous étudions par exemple des capteurs du plan capables de détecter des défaillances `a un rayon connu avec une erreur tolérée. Nous donnons des constructions de tels codes et bornons leur taille pour des valeurs de rayons et d'erreurs fixés ou asymptotiques. Nous introduisons enfin la notion de coloration identifiante d'un graphe, permettant d'identifier les sommets d'un graphe avec les couleurs présentes dans son voisinage. Nous comparons cette coloration avec la coloration propre des graphes et donnons des bornes sur le nombre de couleurs nécessaires pour identifier un graphe, pour plusieurs classes de graphes. / In this thesis, we study problems on vertices identification of graphs. To identify the vertices of a graph consists in giving to each vertex of the graph an object that makes it unique. We are specially interested in the problem of identifying codes : dominating sets of vertices for which the closed neighborhood of each vertex has a unique intersection with the set. The vertices of the identifying code can be seen as sensors and each vertex of the graph as the location of a potential fault. We first classify all finite graphs for which all but one of the vertices are needed in any identifying code. Finding an optimal identifying code, i.e, an identifying code of minimum size, is a $NP$-hard problem. Therefore, we study this problem in some restricted classes of graphes. Depending on the class considered, we are able to solve this problem (for Sierpi`nski graphs), to give better bounds on the size of an identifying code than the general one (for interval graphs, line graphs and the king grid) or to prove that the problem remains NP-hard even in the restricted class (for line graphs). Then, we consider some variations of identifing codes that give flexibility to the sensors. For example, we study codes sensors able to detect faults within a radius around a fixed value. We give constructions of such codes and bounds on their size for general and asymptotic values of the radius and the tolerance on it. Finally, we introduce identifying colourings of graphs; verex-colouring of graph such that each vertex is identified by the set of colours in its closed neighbourhood. We compare this colouring of graphs with proper vertex-coloring and give bounds on the number of colours required to identify a graph, for several class of graphs.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / The coloring problem is among the most studied in the Graph Theory due to its great theoretical and practical importance. Since the problem of coloring the vertices of a graph G either with the smallest amount of colors is NP-hard, various coloring heuristics are examined to obtain a proper colouring with a reasonably small number of colors. Given a graph G, the b heuristic of colouring comes down to decrease the amount of colors in a proper colouring c, so that, if all vertices of a color class fail to see any color in your neighborhood, then we can change the color to any color these vertices nonexistent in your neighborhood. Thus, we obtain a coloring c ′ with a color unless c. Irving and Molove defined the b-coloring of a graph G as a coloring where every color class has a vertex that is adjacent the other color classes. These vertices are called b-vertices. Irving and Molove also defined the b-chromatic number as the largest integer k, such that G admits a b-coloring by k colors. They showed that determine the value of the b-chromatic number of any graph is NP-hard, but polynomial for trees. Irving and Molove also defined the m-degree of a graph, which is the largest integer m(G) such that there are m(G) vertices with degree at least m(G) − 1. Irving and Molove showed that the m-degree is an upper limit to the b-chromatic number and showed that it is m(T) or m(T)−1 to every tree T, where its value is m(T) if, and only if, T has a good set. In this dissertation, we analyze the relationship between the girth, which is the size of the smallest cycle, and the b-chromatic number of a graph G. More specifically, we try to find the smallest integer g ∗ such that if the girth of G is at least g ∗ , then the b-chromatic number equals m(G) or m(G)−1. Show that the value of g ∗ is at most 6 could be an important step in demonstrating the famous conjecture of Erd˝os-Faber-LovÂasz, but the best known upper limit to g ∗ is 9. We characterize the graphs whose girth is at least 6 and not have a good set and show how b-color them optimally. Furthermore, we show how b-color, also optimally, graphs whose girth is at least 7 and not have good set. / O problema de coloraÃÃo està entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importÃncia teorica e prÃtica. Dado que o problema de colorir os vÃrtices de um grafo G qualquer com a menor quantidade de cores à NP-difÃcil, vÃrias heurÃsticas de coloraÃÃo sÃo estudadas a fim de obter uma coloraÃÃo prÃpria com um nÃmero de cores razoavelmente pequeno. Dado um grafo G, a heurÃstica b de coloraÃÃo se resume a diminuir a quantidade de cores utilizadas em uma coloraÃÃo prÃpria c, de modo que, se todos os vÃrtices de uma classe de cor deixam de ver alguma cor em sua vizinhanÃa, entÃo podemos modificar a cor desses vÃrtices para qualquer cor inexistente em sua vizinhanÃa. Dessa forma, obtemos uma coloraÃÃo c′ com uma cor a menos que c. Irving e Molove definiram a b-coloraÃÃo de um grafo G como uma coloraÃÃo onde toda classe de cor possui um vÃrtice que à adjacente as demais classes de cor. Esses vÃrtices sÃo chamados b-vÃrtices. Irving e Molove tambÃm definiram o nÃmero b-cromÃtico como o maior inteiro k tal que G admite uma b-coloraÃÃo por k cores. Eles mostraram que determinar o nÃmero b-cromÃtico de um grafo qualquer à um problema NP-difÃcil, mas polinomial para Ãrvores. Irving e Molove tambÃm definiram o m-grau de um grafo, que à o maior inteiro m(G) tal que existem m(G) vÃrtices com grau pelo menos m(G)−1. Irving e Molove mostraram que o m-grau à um limite superior para nÃmero b-cromÃtico e mostraram que o mesmo à igual a m(T) ou a m(T)−1, para toda Ãrvore T, onde o nÃmero b-cromÃtico à igual a m(T) se, e somente se, T possui um conjunto bom. Nesta dissertaÃÃo, verificamos a relaÃÃo entre a cintura, que à o tamanho do menor ciclo, e o nÃmero b-cromÃtico de um grafo G. Mais especificamente, tentamos encontrar o menor inteiro g∗ tal que, se a cintura de G à pelo menos g∗, entÃo o nÃmero b-cromÃtico à igual a m(G) ou m(G)−1. Mostrar que o valor de g∗ à no mÃximo 6 poderia ser um passo importante para demonstrar a famosa Conjectura de ErdÃs-Faber-Lovasz, mas o melhor limite superior conhecido para g∗ à 9. Caracterizamos os grafos cuja cintura à pelo menos 6 e nÃo possuem um conjunto bom e mostramos como b-colori-los de forma Ãtima. AlÃm disso, mostramos como bicolorir, tambÃm de forma Ãtima, os grafos cuja cintura à pelo menos 7 e nÃo possuem conjunto bom.

No description available.

No / An opportunity was afforded to analyse pigment specimens from an unrestored oil painting in the style of the English School of the mid-18th Century prior to conservation being undertaken. Raman spectroscopy was adopted to characterise the pigments and indicated the presence of a novel red pigment which was assigned to the complex chromium mineral, hemihedrite, in addition to other interesting materials found in combination. This is the first recorded identification of hemihedrite spectral signals in an art context in a range of mineral pigments that are otherwise typical of this period and some hypotheses are presented to explain its presence based on its occurrence with associated mineral pigments. It is suggested that the presence of powdered glass identified in certain areas of the painting enhanced the reflectivity of the pigment matrix.

Notre objectif est d’évaluer et de rendre opérationnelle la décomposition de problèmes d’optimisation sous contraintes. Nous nous sommes intéressés à deux problèmes en particulier : le problème de la recherche d’un plus grand sous-graphe commun (MCIS), et le problème de somme coloration minimale (MSCP). Il s’agit de problèmes NP-difficiles pour lesquels les approches de résolution complètes passent difficilement à l’échelle, et nous proposons de les améliorer à cet égard en décomposant ces problèmes en sous-problèmes indépendants. Les décompositions que nous proposons s’appuient sur la structure du problème initial pour créer des sous-problèmes de tailles équilibrées. Pour le MCIS, nous introduisons une décomposition basée sur la structure du graphe de compatibilité, et nous montrons que cette décomposition permet d’obtenir des sous-problèmes plus équilibrés que la méthode EPS classiquement utilisée pour paralléliser la résolution de problèmes en programmation par contraintes. Pour le MSCP, nous introduisons une nouvelle décomposition arborescente de hauteur bornée, et nous montrons comment tirer partie de la complémentarité de la programmation par contraintes et de la programmation linéaire en nombres entiers pour obtenir et résoudre les sous-problèmes indépendants qui en découlent. Nous proposons également une approche portfolio qui utilise des techniques d’apprentissage automatique pour choisir dynamiquement l’approche la plus performante en fonction du problème à résoudre. / The objective of this thesis is, from a general standpoint, to design and evaluate decomposition methods for solving constrained optimisation problems. Two optimisation problems in particular are considered: the maximum common induced subgraph problem, in which the largest common part between two graphs is to be found, and the sum colouring problem, where a graph must be coloured in a way that minimises a sum of weights induced by the employed colours. The maximum common subgraph (MCIS) problem is notably difficult, with a strong applicability in domains such as biology, chemistry and image processing, where the need to measure the similarity between structured objects represented by graphs may arise. The outstanding difficulty of this problem makes it strongly advisable to employ a decomposition method, possibly coupled with a parallelisation of the solution process. However, existing decomposition methods are not well suited to solve the MCIS problem: some lead to a poor balance between subproblems, while others, like tree decomposition, are downright inapplicable. To enable the structural decomposition of such problems, Chmeiss et al. proposed an approach, TR-decomposition, acting at a low level: the microstructure of the problem. This approach had yet to be applied to the MCIS problem. We evaluate it in this context, aiming at reducing the size of the search space while also enabling parallelisation. The second problem that caught our interest is the sum colouring problem. It is an NP-hard variant of the widely known classical graph colouring problem. As in most colouring problems, it basically consists in assigning colours to the vertices of a given graph while making sure no neighbour vertices use the same colour. In the sum colouring problem, however, each colour is associated with a weight. The objective is to minimise the sum of the weights of the colours used by every vertex. This leads to generally harder instances than the classical colouring problem, which simply requires to use as few colours as possible. Only a few exact methods have been proposed for this problem. Among them stand notably a constraint programming (CP) model, a branch and bound approach, as well as an integer linear programming (ILP) model. We led an in-depth investigation of CP's capabilities to solve the sum colouring problem, while also looking into ways to make it more efficient. Additionally, we evaluated a combination of integer linear programming and constraint programming, with the intention of conciliating the strong points of these highly complementary approaches. We took inspiration from the classical backtracking bounded by tree decomposition (BTD) approach. We employ a tree decomposition with a strictly bounded height. We then derive profit from the complementarity of our approaches by developing a portfolio approach, able to choose one of the considered approaches automatically by relying on a number of features extracted from each instance.

Submitted by Jorge Silva (jorgelmsilva@ufrrj.br) on 2017-05-19T18:26:23Z No. of bitstreams: 1 2016 - Denise Rosane Perdomo Azeredo.pdf: 2006973 bytes, checksum: 610e1499e6733b78ee2eb47034198a7d (MD5) / Made available in DSpace on 2017-05-19T18:26:23Z (GMT). No. of bitstreams: 1 2016 - Denise Rosane Perdomo Azeredo.pdf: 2006973 bytes, checksum: 610e1499e6733b78ee2eb47034198a7d (MD5) Previous issue date: 2016-08-25 / Nowadays consumer desired healthy foods that promote benefits and free from food additives. The chemical composition of soft drinks, artificial colors and preservative, may pose a risk to consumer health due to the possibility of benzene formation, a recognized carcinogenic agent in humans and the association between artificial colors, allergic reactions and DNA damage. In this study, an orange soda formula containing the preservatives sodium benzoate and potassium sorbate with carrot and apple concentrate was developed. In parallel, we developed a standard formula containing tartrazine and sunset yellow. Physicochemical, microbiological and sensory analysis of formulas were carried out during the storage period of 150 days. It was observed that there were no changes in physicochemical parameters. However, the colorimetric analysis revealed a short shelf life in the sample containing the carrot and apple concentrate. Regarding microbiology, both formulations were according to regulation by public health agencies. The yeasts and molds counts presented 1 log cycle growth in the formula containing the carrot and apple concentrate, suggesting that the robustness of the developed matrix may be affected, if the hygiene conditions of processing line sanitation are not observed. It was found that the color was the sensory characteristic that most influenced consumers regarding the acceptability of the samples, signaling that this parameter interfered significantly in evaluating flavor and appearance The results obtained by microbiological challenge test and determination of growth potential (?) indicated that yeast and lactic acid bacteria are able to multiply in the formula containing carrot and apple concentrate without preservatives (? ? 0.5 log10), indicating that the formula is sensitive. Acid acetic bacteria, in these conditions, were inhibited. A preserved formula with the addition of carrot and apple concentrate and other formula with the addition of artificial colors were prepared. The results referring to the growth potential (?) indicated that yeast and lactic acid bacteria were inhibited (? ? 0.5 log10) in both formulas. However, the preservative resistant yeasts presented growth ability (? ? 0.5 log10). In the apple and carrot concentrate, it was observed that yeast, lactic acid bacteria and fungus Penicillium citrinum were inhibited, indicating that this ingredient should not be considered a nutrient source for microbial multiplication that would affect the formula robustness. It was verified the growth of the preservative resistant yeasts (growth potential ? ? 0,5 log10) in all the evaluated formulas and ingredient. The data obtained, in this study, indicate that the development of more natural foods still represents a challenge for the food industry. / Atualmente o consumidor anseia por alimentos mais naturais, saud?veis, que promovam benef?cios ? sa?de e que sejam isentos de aditivos. Nesse sentido, a composi??o qu?mica dos refrigerantes, especialmente no que concerne aos corantes artificiais e conservadores pode representar riscos ? sa?de do consumidor, devido a possibilidade de forma??o de benzeno, reconhecido agente carcinog?nico ao homem, e a associa??o entre corantes artificiais, rea??es al?rgicas e efeitos delet?rios ao DNA. Nessa pesquisa, inicialmente, desenvolveu-se uma formula??o de refrigerante de laranja, contendo os conservadores benzoato de s?dio e sorbato de pot?ssio, na qual os corantes artificiais ? amarelo tartrazina e amarelo crep?sculo foram substitu?dos por concentrado de cenoura e ma??. Em paralelo, desenvolveu-se uma formula??o controle. Foram realizadas an?lises f?sico-qu?micas, microbiol?gicas e sensorial das formula??es durante o per?odo de armazenamento de 150 dias. Observou-se o atendimento ao padr?o de identidade e qualidade e estabilidade das formula??es em rela??o aos par?metros f?sico-qu?micos. Entretanto, na an?lise colorim?trica observou-se uma degrada??o de cor percept?vel ao consumidor na amostra contendo o concentrado de cenoura e ma??. Em rela??o as an?lises microbiol?gicas, ambas as formula??es atenderam aos par?metros preconizados pela legisla??o. Entretanto, a contagem de bolores e leveduras apresentou crescimento de 1 ciclo log na formula??o contendo o concentrado de cenoura e ma??, sugerindo que a robustez da matriz desenvolvida pode ser afetada, se as condi??es de higieniza??o da linha de processamento n?o forem observadas. Em rela??o a an?lise sensorial, verificou-se que a cor foi a caracter?stica sensorial que mais influenciou os consumidores com rela??o a aceitabilidade das amostras, sinalizando que esse par?metro interferiu, de forma significativa na avalia??o do sabor e apar?ncia. Os resultados referentes a aplica??o do teste desafio e a determina??o do potencial de multiplica??o microbiana (?) indicaram que as leveduras e bact?rias l?cticas s?o capazes de se multiplicar na formula??o adicionada de concentrada de cenoura e ma?? sem conservadores (? ? 0,5 log10), sinalizando que a formula??o ? sens?vel. As bact?rias ac?ticas, nessas condi??es, foram inibidas. Nas formula??es preservadas quimicamente com adi??o de concentrado de cenoura e ma?? e a adicionada de corantes artificiais, os resultados referentes ao potencial de multiplica??o microbiana (?) indicaram que as leveduras e bact?rias l?cticas foram inibidas (? ? 0,5 log10) em ambas as formula??es. Entretanto, as leveduras resistentes a conservadores apresentaram habilidade de crescimento (? ? 0,5 log10). No ingrediente concentrado de cenoura e ma??, observou-se que as leveduras, bact?rias l?cticas e o fungo Penicillium citrinum foram inibidos, indicando que o concentrado n?o deve ser considerado uma fonte de nutriente para a multiplica??o microbiana que afetaria a robustez da formula??o. Constatou-se a multiplica??o das leveduras resistentes a conservadores, com potencial de multiplica??o ? ? 0,5 log10 em todas as formula??es e ingrediente avaliados. Os dados obtidos no presente estudo sinalizam que o desenvolvimento de alimentos mais naturais ainda representa um desafio para a ind?stria de alimentos.

In this thesis, we will discuss the construction of algorithms for solving Constraint Satisfaction Problems (CSPs), and describe two new ways of approaching them. Both approaches are based on the idea that it is sometimes faster to solve a large number of restricted problems than a single, large, problem. One of the strong points of these methods is that the intuition behind them is fairly simple, which is a definite advantage over many techniques currently in use. The first method, the covering method, can be described as follows: We want to solve a CSP with n variables, each having a domain with d elements. We have access to an algorithm which solves problems where the domain has size e < d, and we want to cover the original problem using a number of restricted instances, in such a way that the solution set is preserved. There are two ways of doing this, depending on the amount of work we are willing to invest; either we construct an explicit covering and end up with a deterministic algorithm for the problem, or we use a probabilistic reasoning and end up with a probabilistic algorithm. The second method, called the partitioning method, relaxes the demand on the underlying algorithm. Instead of having a single algorithm for solving problems with domain less than d, we allow an arbitrary number of them, each solving the problem for a different domain size. Thus by splitting, or partitioning, the domain of the large problem, we again solve a large number of smaller problems before arriving at a solution. Armed with these new techniques, we study a number of different problems; the decision problems (d, l)-CSP and k-Colourability, together with their counting counterparts, as well as the optimisation problems Max Ind CSP, Max Value CSP, Max CSP, and Max Hamming CSP. Among the results, we find a very fast, polynomial space algorithm for determining k-colourability of graphs.

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 <i>P</i> and <i>Q</i> are additive induced-hereditary graph families, then (<i>P</i>,<i>Q</i>)-COLOURING is NP-hard, with the exception of GRAPH 2-COLOURING. Moreover, with the same exception, (<i>P</i>,<i>Q</i>)-COLOURING is NP-complete iff <i>P</i>- and <i>Q</i>-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 <i>vice versa</i>; · extensions of Mihók's construction of uniquely colourable graphs, and Scheinerman'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 <i>G</i> is a generating set for <i>A</i> &#959; <i>B</i>, where <i>A</i> and <i>B</i> are indiscompositive, then we can extract generating sets for <i>A</i> and <i>B</i> using a <i>greedy algorithm</i>.

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 <i>P</i> and <i>Q</i> are additive induced-hereditary graph families, then (<i>P</i>,<i>Q</i>)-COLOURING is NP-hard, with the exception of GRAPH 2-COLOURING. Moreover, with the same exception, (<i>P</i>,<i>Q</i>)-COLOURING is NP-complete iff <i>P</i>- and <i>Q</i>-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 <i>vice versa</i>; · extensions of Mihók's construction of uniquely colourable graphs, and Scheinerman'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 <i>G</i> is a generating set for <i>A</i> &#959; <i>B</i>, where <i>A</i> and <i>B</i> are indiscompositive, then we can extract generating sets for <i>A</i> and <i>B</i> using a <i>greedy algorithm</i>.