This thesis discusses colouring, circular list colouring and adapted game colouring of graphs. For colouring, this thesis obtains a sufficient condition for a planar graph to be 3-colourable. Suppose G is a planar graph. Let H_G be the graph with vertex set V (H_G) = {C : C is a cycle of G with |C| ∈ {4, 6, 7}} and edge set E(H_G) = {CiCj : Ci and Cj have edges in common}. We prove that if any 3-cycles and 5-cycles are not adjacent to i-cycles for 3 ≤ i ≤ 7, and H_G is a forest, then G is 3-colourable. For circular consecutive choosability, this thesis obtains a basic relation among chcc(G), X(G) and Xc(G) for any finite graph G. We show that for any finite graph G, X(G) − 1 ≤ chcc(G) < 2 Xc(G). We also determine the value of chcc(G) for complete graphs, trees, cycles, balanced complete bipartite graphs and some complete multi-partite graphs. Upper and lower bounds for chcc(G) are given for some other classes of graphs. For adapted game chromatic number, this thesis studies the adapted game chromatic number of various classes of graphs. We prove that the maximum adapted game chromatic number of trees is 3; the maximum adapted game chromatic number of outerplanar graphs is 5; the maximum adapted game chromatic number of partial k-trees is between k + 2 and 2k + 1; and the maximum adapted game chromatic number of planar graphs is between 6 and 11. We also give upper bounds for the Cartesian product of special classes of graphs, such as the Cartesian product of partial k-trees and outerplanar graphs, or planar graphs.

LIMA, Carlos Vinicius Gomes Costa. Sobre b-coloração de grafos com cintura pelo menos 6. 2013. 59 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza- Ceará, 2013. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-13T18:53:18Z No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-13T19:18:47Z (GMT) No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) / Made available in DSpace on 2016-06-13T19:18:47Z (GMT). No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) Previous issue date: 2013 / 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. / 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.

Arisen from the Pure Parsimony Haplotyping problem in the bioinformatics, we developed the Minimum Rainbow Subgraph problem (MRS problem): Given a graph $G$, whose edges are coloured with $p$ colours. Find a subgraph $F\\\\subseteq G$ of $G$ of minimum order and with $p$ edges such that each colour occurs exactly once. We proved that this problem is NP-hard, and even APX-hard. Furthermore, we stated upper and lower bounds on the order of such minimum rainbow subgraphs. Several polynomial-time approximation algorithms concerning their approximation ratio and complexity were discussed. Therefore, we used Greedy approaches, or introduced the local colour density $\\\\lcd(T,S)$, giving a ratio on the number of colours and the number of vertices between two subgraphs $S,T\\\\subseteq G$ of $G$. Also, we took a closer look at graphs corresponding to the original haplotyping problem and discussed their special structure.:Mathematics and biology - having nothing in common? I. Going for a start 1. Introducing haplotyping 2. Becoming mathematical II. The MRS problem 3. The graph theoretical point of view 3.1. The MRS problem 3.2. The MRS problem on special graph classes 4. Trying to be not that bad 4.1. Greedy approaches 4.2. The local colour density 4.3. MaxNewColour 5. What is real data telling us? And the work goes on and on Bibliography

For a set of graphs H, we call a graph G H-free if G-S is non-isomorphic to H for each S⊆V(G) and each H∈H. Let f_H^* ∶N_(>0)↦N_(>0 )be the optimal χ-binding function of the class of H-free graphs, that is, f_H^* (ω)=max⁡{χ(G): ω(G)=ω,G is H-free} where χ(G),ω(G) denote the chromatic number and clique number of G, respectively. In this thesis, we mostly determine optimal χ-binding functions for subclasses of P_5-free graphs, where P_5 denotes the path on 5 vertices. For multiple subclasses we are able to determine them exactly and for others we prove the right order of magnitude. To achieve those results we prove structural results for the graph classes and determine colourings. We sometimes obtain those results by researching the prime graphs and combining the two decomposition methods by homogeneous sets and clique-separators. Additionally, we use the Strong Perfect Graph Theorem and analyse the neighbourhood of holes. For some of these subclasses we characterise all graphs G with χ(G)>χ(G-\{u\}), for each u∈V(G) and use those to determine the function.

Krivelevich and Patkós conjectured in 2009 that χ(G(n, p)) ∼ χ=(G(n, p)) ∼ χ∗=(G(n, p)) for C/n < p < 1 − ε, where ε > 0. We prove this conjecture for n−1+ε1 < p < 1 − ε2 where ε1, ε2 > 0. We investigate several measures that have been proposed to indicate centrality of nodes in networks, and find examples of networks where they fail to distinguish any of the vertices nodes from one another. We develop a new method to investigate core-periphery structure, which entails identifying densely-connected core nodes and sparsely-connected periphery nodes. Finally, we present an experiment and an analysis of empirical networks, functional human brain networks. We found that reconfiguration patterns of dynamic communities can be used to classify nodes into a stiff core, a flexible periphery, and a bulk. The separation between this stiff core and flexible periphery changes as a person learns a simple motor skill and, importantly, it is a good predictor of how successful the person is at learning the skill. This temporally defined core-periphery organisation corresponds well with the core- periphery detected by the method that we proposed earlier the static networks created by averaging over the subjects dynamic functional brain networks.

Au cours de l’élaboration des peintures rupestres, divers matériaux colorants peuvent être mobilisés et produire des vestiges archéologiques liés aux différentes étapes de la préparation de la matière picturale. À Nawarla Gabarnmang, site majeur d’art rupestre Jawoyn (Terre d’Arnhem, Territoire du Nord – Australie), les fouilles archéologiques ont mis au jour un grand nombre de ce type de vestiges. La séquence archéologique, obtenue par datation au 14C, a révélé la présence de dépôts culturels parmi les plus anciens connus en Australie, avec une occupation du site qui s’étend de ≥48 000 ans cal BP jusqu’au début du XXème siècle. Plafonds et piliers du site présentent plusieurs générations de peintures ; les plafonds du site contiennent à eux seuls près de 1400 entités graphiques. La place de cet art interroge : est-il l’expression des premiers Hommes arrivés sur le continent australien il y a près de 50 000 ans ou le témoin d’occupations plus récentes ? Caractérisé par la superposition de plusieurs générations de peintures qu’on ne peut dater de manière « directe » en raison de la nature minéralogique des composants des peintures, la définition de leur chronologie constitue un fort enjeu de recherche. Menés d’emblée dans une approche intégrée, les premiers travaux ont permis d’étudier la chronologie et la nature des occupations, via les fouilles archéologiques, d’identifier les aménagements réalisés au cours des différentes phases d’occupation et de mettre en avant la richesse et la diversité de son répertoire artistique de même que l’abondance et la variété des vestiges associés à l’art rupestre. Afin d’appréhender au mieux la temporalité et les usages du site de Nawarla Gabarnmang depuis les premières occupations préhistoriques jusqu’aux fréquentations subactuelles, l’analyse des matières colorantes et colorées, retrouvées dans les carrés de fouille réalisés sous les panneaux peints des plafonds ou à l’aplomb des piliers décorés, permet de reconstituer les étapes de la chaîne opératoire ayant produit les matières picturales : de la source d’approvisionnement en matières premières, aux modes de transformation et de préparation (broyage, mélange avec charges et/ou liants, traitement thermique) jusqu’à leur application. La stratégie méthodologique mise en place couvre un large panel de techniques de caractérisation physico-chimique pour répondre aux problématiques soulevées par les différents vestiges associés à l’art rupestre. De l’observation macroscopique aux micro-analyses non invasives couplées à des analyses structurales, en passant par des techniques basées sur le rayonnement synchrotron, l’étude menée sur les matières colorantes et colorées a permis de révéler une diversité et une complexité de phases minérales utilisées dans l’art rupestre de Nawarla Gabarnmang. Croisée avec les données archéologiques, anthropo-géomorphologiques et pariétales, elle permet de proposer un cadre chronologique des différentes générations de peintures en lien avec les phases d’occupation qui ont marqué l’histoire du site. L’analyse des matières colorantes et colorées réalisée au cours de cette thèse constitue un vecteur de connaissances importantes et livre des informations complémentaires aux approches archéologique, géomorphologique et pariétale menées sur le site de Nawarla Gabarnmang. Les informations apportées par l’étude de ces matières permettent de renseigner tant sur les évolutions techniques et comportementales que sur l’implication culturelle de ce site, aussi bien dans ses dimensions spatiales que temporelles. / In the making of rock art, raw colouring material is used, thus providing many artifacts related to different steps of elaboration of pictorial matter. In the case of the important rock art site of Nawarla Gabarnmang in the Jawoyn country (Arnhem Land, North Territory – Australia), excavations have revealed a large number of such artifacts. The archaeological sequence from the floor deposits, radiocarbon-dated from ≥48,000 cal BP to the early twentieth century, has revealed some of the oldest known cultural deposits in Australia. The ceilings of the site contain well over 1400 still-visible paintings in multiple, superimposed layers. Countless additional paintings cover many of the rock pillars’ walls. This art raises questions: is it an expression of the first humans arrived on the Australian continent 50,000 years ago, or the evidence of recent occupation periods? Characterized by a succession of overlaid motifs, which cannot be “directly” dated because of the mineralogical nature of the rock paintings’ components, the determination of the age of the rock paintings represents a major issue. Through an integrated approach to the matter, the first results of the archaeological excavations enabled to study the chronology and the nature of activities, to identify the origins and transformations of the sheltered space through time, to highlight the richness and the diversity of its artistic work, as well as the abundance and the variety of the artifacts. To get a better insight into the temporality and the uses of Nawarla Gabarnmang since the first prehistoric activities until the recent periods, the analysis of the colouring and coloured matters, found in trial excavations under the painted panels on the ceilings or at the bottom of decorated pillars, allow us to rebuild the steps of the “chaîne opératoire” leading to the production of pictorial matter: from the sources of raw materials, the methods of transformation and preparation (grinding, mixing with mineral extenders and/or organic binders, heat treatment), to the application on the rock. To answer the questions raised by different artifacts, the methodological strategy includes a large range of microscopic and spectroscopic approaches. Subjected to macroscopic observations and non-invasive micro-analytical techniques along with structural techniques, as well as techniques using synchrotron radiation, the analysis of the colouring and coloured matters has revealed the variety and the complexity of mineral compounds used in the rock art of Nawarla Gabarnmang. Then, cross-referenced with archaeological, archaeomorphological and rock art studies, the physico-chemical characterization allows to suggest a chronological framework for the different superimposed layers linked to the periods of activities that marked the history of the site. The analysis of colouring and coloured matters undertaken by this thesis represents an important source of knowledge and delivers further informations to the geomorphological, archaeological and rock art studies carried out at the Nawarla Gabarnmang. The results provided by the study of these materials bring information as well on technical and behavioral evolutions, as on the cultural involvement of this site, not only in its spatial but also in its temporal dimensions.

Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques.La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum ID est n-1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour le paramètre ID dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ID dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits. / In this thesis we study three theoretical computer science problems, namely the orthogonal packing problem (OPP for short), strong edge-colouring and identifying codes.OPP consists in testing whether a set of rectangular items can be packed in a rectangular container without overlapping and without exceeding the borders of this container. An additional constraint is that the rotation of the items is not allowed. The problem is NP-hard even when the problem is reduced to packing squares in a square. We propose an exact algorithm for solving OPP efficiently using the characterization of the problem by interval graphs proposed by Fekete and Schepers. For this purpose we use some compact representation of interval graphs - MPQ-trees. We show experimental results of our approach by comparing them to the results of other algorithms known in the literature. we observe promising gains.The study of strong edge-colouring and identifying codes is focused on the structural and computational aspects of these combinatorial problems. In the case of strong edge-colouring we are interested in the families of planar graphs and subcubic graphs. We show optimal upper bounds for the strong chromatic index of subcubic graphs as a function of the maximum average degree. We also show that every planar subcubic graph without induced cycles of length 4 and 5 can be strong edge-coloured with at most nine colours. Finally, we confirm the difficulty of the problem by showing that it remains NP-complete even in some restricted classes of planar subcubic graphs.For the subject of identifying codes we propose a characterization of non-trivial graphs having maximum identifying code number ID, that is n-1, where n is the number of vertices. We study the case of line graphs and prove lower and upper bounds for ID parameter in this class. At last we investigate the complexity of the corresponding decision problem and show the existence of a linear algorithm for computing ID of the line graph L(G) where G has the size of the tree-width bounded by a constant. On the other hand, we show that the identifying code problem is NP-complete in various subclasses of planar graphs.

Les matières colorantes sont des vestiges encore mal connus de nos jours. L'intérêt qu'elles suscitent tient à ce qu'elles sont susceptibles de révéler des pratiques techniques diverses et complexes, mais il tient aussi à leur forte potentialité à traduire des pratiques symboliques du fait de leur pouvoir colorant intense et des couleurs exploitées : le rouge et le noir qui sont encore aujourd'hui investis d'une forte valeur symbolique. Dans un contexte aussi particulier que celui de la transition entre le Paléolithique moyen et le Paléolithique supérieur, ces vestiges ont été mis au jour en abondance et demandent à être analysés pour restituer les modes de vie des derniers hommes de Neandertal. C'est sur le gisement châtelperronien de la grotte du Renne à Arcy-sur-Cure (Yonne), fouillé de 1949 à 1963 par André Leroi-Gourhan, que les nombreuses matières colorantes découvertes ont conduit à échafauder des théories concernant leurs transformations et leurs utilisations qui méritaient d'être éprouvées. En effet, il est supposé, depuis leur découverte, qu'elles ont fait l'objet d'un chauffage contrôlé qui visait à en modifier la couleur, le chauffage permettant de transformer les matières colorantes jaunes en orangées, en rouges et en violacés. De cette hypothèse découle la théorie selon laquelle les Néandertaliens ont exploité les matières colorantes en tant que pigment pour des réalisations symboliques, voire d'ordre esthétique, ce qui n'a pas encore pu être prouvé. Notre étude, fondée sur le croisement des données issues des analyses de la nature physico-chimique et pétrographique des assemblages de matières colorantes, mais aussi sur leur intégration dans le gisement, en association avec des structures d'habitat dont la conservation est exceptionnelle, et sur une série d'expérimentations visant à caractériser les poudres obtenues par différents moyens (broyage et concassage d'une part, abrasion d'autre part) ont permis de définir les choix techniques qui ont présidé à l'approvisionnement en matières colorantes dans tous les niveaux d'occupation châtelperroniens de la grotte du Renne. Il a ainsi été possible de démontrer qu'aucune des matières colorantes, rouges ou noires, n'a fait l'objet d'un chauffage préalablement à son utilisation, bien au contraire de ce qui avait été supposé jusqu'ici. Ces matières colorantes ont fait l'objet d'un approvisionnement raisonné auprès de formations géologiques affleurant ponctuellement à plus de 10~km et à environ 5~km de la grotte. L'exploitation de ces gîtes de matières premières colorantes a été la même durant toute la séquence châtelperronienne et s'est orientée préférentiellement vers des matériaux que l'on peut aisément réduire en poudre. Une partie était grossièrement réduite en poudre afin de recouvrir de grandes surfaces (sols, peaux de bêtes) dans le but de les assainir, alors qu'une autre partie des matières colorantes était destinée à des activités plus minutieuses nécessitant leur emploi sous forme d'une poudre fine, régulière et extrêmement colorante. Dans ce dernier cas, les Néandertaliens de la grotte du Renne ont entrepris d'exploiter ces produits en association avec le travail des matières osseuses (os et ivoire de mammouth) mais aussi pour leur couleur. L'assemblage des matières colorantes de la grotte du Renne révèle un profond ancrage des connaissances et de la compréhension des multiples propriétés et qualités des matières colorantes intensément mises à profit de telle sorte que le gisement châtelperronien était tout de rouge et noir et la chaîne opératoire qu'il été possible de restituer relève d'inventions techniques abouties, très élaborées dans leur genre pour l'état des observations ingénieuses, des découvertes et donc de la pensée qu'elles supposent et des capacités dont elles témoignent. / Despite an increasing number of studies, colouring materials are still poorly understood among excavation remains. Their attraction lies in their capacity to bring to light diverse and complex skills, but also in their intense colouring power and their contrasting colours: red and black, which still possess a symbolic value. These highly-symbolic materials may, therefore, highlight the “conceptual” practices of prehistoric men and give access to their symbolic world and thought. In such a particular context as the transition between the Middle and the Upper Palaeolithic, these remains, which are very abundant in most excavations, offer the possibility, through analysis, to get an exceptional insight into the way of life of the last Neanderthals. The Châtelperronian site of the “Grotte du Renne”, in Arcy-sur-Cure (Yonne), is a landmark. It was excavated beween 1949 and 1963 by André Leroi-Gourhan: Numerous colouring materials were discovered there, and Leroi-Gourhan developed theories about their transformation and uses which so far have not been tested, and have remained unchallenged. Since their discovery, the assumption is that those minerals were heated in a controlled way, in order to modify their colour. It is indeed well-known that heat transforms yellow materials (iron oxides) in orange, red or purple materials (other iron oxides). From this hypothesis originates the theory according to which Neanderthals exploited colouring materials as pigments for symbolic or even aesthetic purposes. But the theory has so far never been proved true. Our study combines several sets of data, obtained from different methods. Physico-chemical and petrological analyses were carried out on the colouring materials. These data were related to their location on the site, in association with exceptionally well preserved “hut” structures. Furthermore, a series of experimentations, aimed to characterize powders obtained via different methods (grinding and crushing on the one hand, abrasion on the other hand). The comparison of all these data enabled us to identify the various technical choices which informed the supply in colouring minerals in all the Châtelperronian levels of the Grotte du Renne. It was thus possible to demonstrate that none of these materials, either red or black, was heated before being used, contrary to what had been assumed so far. The supply in colouring materials was as carefully organised as for other materials (flint, for example); they were collected in geological formations occasionally showing on the surface, at more than 10 km from the cave. The exploitation of these geological sites did not vary during the whole Châtelperronian period, and privileged materials which can easily be ground into powder. Part of their supply was ground coarsely in order to cover large surface areas (soils or hides) as preservative or to clean them up. The remaining materials were destined to more meticulous activities, which required a fine, regular, and highly-colouring powder. In this latter case, the Neanderthals of the Grotte du Renne used those products when working on bone materials (bone or mammoth ivory), and used them also for their sheer colour. The set of colouring minerals from the Grotte du Renne reveals Neanderthals’ in-depth knowledge of materials; they understood perfectly well their properties and qualities, and used them extensively, so that the Châtelperronian site must have been a literally dazzling sight, all red and black. The “chaîne opératoire” which transpires from our analysis shows very sophisticated techniques, and an advanced “technological” knowledge. They are witness to surprising capacities and a highly-evolved pattern of thought. Keywords: Colouring materials; Ochre; Haematite; Manganese; Middle/Upper Palaeolothic transition; Châtelperronian; Arcy-sur-Cure; Grotte du Renne; Heating; Grinding; Skhul; Les Maîtreaux; Combe Saunière.

This thesis is primarily focused on problems in extremal combinatorics, although we will also consider some questions of analytic and algorithmic nature. The d-dimensional hypercube is the graph with vertex set {0,1}^d where two vertices are adjacent if they differ in exactly one coordinate. In Chapter 2 we obtain an upper bound on the 'saturation number' of Q_m in Q_d. Specifically, we show that for m &ge; 2 fixed and d large there exists a subgraph G of Q_d of bounded average degree such that G does not contain a copy of Q_m but, for every G' such that G &subne; G' &sube; Q_d, the graph G' contains a copy of Q_m. This result answers a question of Johnson and Pinto and is best possible up to a factor of O(m). In Chapter 3, we show that there exists &epsilon; &gt; 0 such that for all k and for n sufficiently large there is a collection of at most 2^{(1-&epsilon;)k} subsets of [n] which does not contain a chain of length k+1 under inclusion and is maximal subject to this property. This disproves a conjecture of Gerbner, Keszegh, Lemons, Palmer, P&aacute;lv&ouml;lgyi and Patk&oacute;s. We also prove that there exists a constant c &isin; (0,1) such that the smallest such collection is of cardinality 2^{(1+o(1))^ck} for all k. In Chapter 4, we obtain an exact expression for the 'weak saturation number' of Q_m in Q_d. That is, we determine the minimum number of edges in a spanning subgraph G of Q_d such that the edges of E(Q_d)\E(G) can be added to G, one edge at a time, such that each new edge completes a copy of Q_m. This answers another question of Johnson and Pinto. We also obtain a more general result for the weak saturation of 'axis aligned' copies of a multidimensional grid in a larger grid. In the r-neighbour bootstrap process, one begins with a set A₀ of 'infected' vertices in a graph G and, at each step, a 'healthy' vertex becomes infected if it has at least r infected neighbours. If every vertex of G is eventually infected, then we say that A₀ percolates. In Chapter 5, we apply ideas from weak saturation to prove that, for fixed r &ge; 2, every percolating set in Q_d has cardinality at least (1+o(1))(d choose r-1)/r. This confirms a conjecture of Balogh and Bollob&aacute;s and is asymptotically best possible. In addition, we determine the minimum cardinality exactly in the case r=3 (the minimum cardinality in the case r=2 was already known). In Chapter 6, we provide a framework for proving lower bounds on the number of comparable pairs in a subset S of a partially ordered set (poset) of prescribed size. We apply this framework to obtain an explicit bound of this type for the poset &Vscr;(q,n) consisting of all subspaces of &Fopf;_qⁿordered by inclusion which is best possible when S is not too large. In Chapter 7, we apply the result from Chapter 6 along with the recently developed 'container method,' to obtain an upper bound on the number of antichains in &Vscr;(q,n) and a bound on the size of the largest antichain in a p-random subset of &Vscr;(q,n) which holds with high probability for p in a certain range. In Chapter 8, we construct a 'finitely forcible graphon' W for which there exists a sequence (&epsilon;_i)^&infin;_i=1 tending to zero such that, for all i &ge; 1, every weak &epsilon;_i-regular partition of W has at least exp(&epsilon;_i^-2/2^{5log&lowast;&epsilon;_i^-2}) parts. This result shows that the structure of a finitely forcible graphon can be much more complex than was anticipated in a paper of Lov&aacute;sz and Szegedy. For positive integers p,q with p/q &VerticalSeparator;&ge; 2, a circular (p,q)-colouring of a graph G is a mapping V(G) &rarr; &Zopf;_p such that any two adjacent vertices are mapped to elements of &Zopf;_p at distance at least q from one another. The reconfiguration problem for circular colourings asks, given two (p,q)-colourings f and g of G, is it possible to transform f into g by recolouring one vertex at a time so that every intermediate mapping is a p,q-colouring? In Chapter 9, we show that this question can be answered in polynomial time for 2 &le; p/q &LT; 4 and is PSPACE-complete for p/q &ge; 4.

Cette thèse réunit en trois articles mon intérêt éclectique pour la théorie des graphes. Le premier problème étudié est la conjecture de Erdos-Faber-Lovász: La réunion de k graphes complets distincts, ayant chacun k sommets, qui ont deux-à-deux au plus un sommet en commun peut être proprement coloriée en k couleurs. Cette conjecture se caractérise par le peu de résultats publiés. Nous prouvons qu’une nouvelle classe de graphes, construite de manière inductive, satisfait la conjecture. Le résultat consistera à présenter une classe qui ne présente pas les limitations courantes d’uniformité ou de régularité. Le deuxième problème considère une conjecture concernant la couverture des arêtes d’un graphe: Si G est un graphe simple avec alpha(G) = 2, alors le nombre minimum de cliques nécessaires pour couvrir l’ensemble des arêtes de G (noté ecc(G)) est au plus n, le nombre de sommets de G. La meilleure borne connue satisfaite par ecc(G) pour tous les graphes avec nombre d’indépendance de deux est le minimum de n + delta(G) et 2n − omega(racine (n log n)), où delta(G) est le plus petit nombre de voisins d’un sommet de G. Notre objectif a été d’obtenir la borne ecc(G) <= 3/2 n pour une classe de graphes la plus large possible. Un autre résultat associé à ce problème apporte la preuve de la conjecture pour une classe particulière de graphes: Soit G un graphe simple avec alpha(G) = 2. Si G a une arête dominante uv telle que G \ {u,v} est de diamètre 3, alors ecc(G) <= n. Le troisième problème étudie le jeu de policier et voleur sur un graphe. Presque toutes les études concernent les graphes statiques, et nous souhaitons explorer ce jeu sur les graphes dynamiques, dont les ensembles d’arêtes changent au cours du temps. Nowakowski et Winkler caractérisent les graphes statiques pour lesquels un unique policier peut toujours attraper le voleur, appellés cop-win, à l’aide d’une relation <= définie sur les sommets de ce graphe: Un graphe G est cop-win si et seulement si la relation <= définie sur ses sommets est triviale. Nous adaptons ce théorème aux graphes dynamiques. Notre démarche nous mène à une relation nous permettant de présenter une caractérisation des graphes dynamiques cop-win. Nous donnons ensuite des résultats plus spécifiques aux graphes périodiques. Nous indiquons aussi comment généraliser nos résultats pour k policiers et l voleurs en réduisant ce cas à celui d’un policier unique et un voleur unique. Un algorithme pour décider si, sur un graphe périodique donné, k policiers peuvent capturer l voleurs découle de notre caractérisation. / This thesis represents in three articles my eclectic interest for graph theory. The first problem is the conjecture of Erdos-Faber-Lovász: If k complete graphs, each having k vertices, have the property that every pair of distinct complete graphs have at most one vertex in common, then the vertices of the resulting graph can be properly coloured by using k colours. This conjecture is notable in that only a handful of classes of EFL graphs are proved to satisfy the conjecture. We prove that the Erdos-Faber-Lovász Conjecture holds for a new class of graphs, and we do so by an inductive argument. Furthermore, graphs in this class have no restrictions on the number of complete graphs to which a vertex belongs or on the number of vertices of a certain type that a complete graph must contain. The second problem addresses a conjecture concerning the covering of the edges of a graph: The minimal number of cliques necessary to cover all the edges of a simple graph G is denoted by ecc(G). If alpha(G) = 2, then ecc(G) <= n. The best known bound satisfied by ecc(G) for all the graphs with independence number two is the minimum of n + delta(G) and 2n − omega(square root (n log n)), where delta(G) is the smallest number of neighbours of a vertex in G. In this type of graph, all the vertices at distance two from a given vertex form a clique. Our approach is to extend all of these n cliques in order to cover the maximum possible number of edges. Unfortunately, there are graphs for which it’s impossible to cover all the edges with this method. However, we are able to use this approach to prove a bound of ecc(G) <= 3/2n for some newly studied infinite families of graphs. The third problem addresses the game of Cops and Robbers on a graph. Almost all the articles concern static graphs, and we would like to explore this game on dynamic graphs, the edge sets of which change as a function of time. Nowakowski and Winkler characterize static graphs for which a cop can always catch the robber, called cop-win graphs, by means of a relation <= defined on the vertices of such graphs: A graph G is cop-win if and only if the relation <= defined on its vertices is trivial. We adapt this theorem to dynamic graphs. Our approach leads to a relation, that allows us to present a characterization of cop-win dynamic graphs. We will then give more specific results for periodic graphs, and we will also indicate how to generalize our results to k cops and l robbers by reducing this case to one with a single cop and a single robber. An algorithm to decide whether on a given periodic graph k cops can catch l robbers follows from our characterization.