Cette thèse présente des résultats obtenus dans deux domaines : la théorie des langages, et la théorie des graphes. En théorie des langages, on s’intéresse à des problèmes de caractérisation de classes de langages réguliers. Le problème générique consiste à déterminer si un langage régulier donné peut être défini dans un certain formalisme. Les méthodes actuelles font intervenir un problème plus général appelé séparation. On présente ici deux types de contributions : une généralisation d’un résultat de décidabilité au cadre des langages de mots infinis, ainsi que des bornes inférieures pour la complexité du problème de séparation. En théorie des graphes, on considère le problème classique de coloration de graphes, où on cherche à attribuer des couleurs aux sommets d’un graphe de sorte que les sommets adjacents reçoivent des couleurs différentes, le but étant d’utiliser le moins de couleurs possible. Dans le cas des graphes peu denses, la méthode de déchargement est un atout majeur. Elle a notamment joué un rôle décisif dans la preuve du théorème des quatre couleurs. Cette méthode peut être vue comme une construction non conventionnelle d’un schéma de preuve par induction, spécifique à la classe de graphes et à la propriété considérées, et où la validité du schéma est rarement immédiate. On utilise des variantes de la méthode de déchargement pour étudier deux types de problèmes de coloration. / In this thesis, we present results obtained in two fields: formal language theory and graph theory. In formal language theory, we consider some problems of characterization of classes of regular languages. The generic problem consists in determining whether a given regular language can be defined in a fixed formalism. The current approaches use a more general problem called separation. We present here two types of contributions: a generalization of a decidability result to the setting of infinite words, together with lower bounds for the complexity of the separation problem. In graph theory, we consider the classical problem of graph coloring, where we assign colors to vertices of a graph in such a way that two adjacent vertices receive different colors. The goal is to use the fewest colors. When the graphs are sparse, a crucial tool for this is the discharging method. It is most notably decisive in the proof of the Four-Color Theorem. This method can be seen as an unconventional construction of an inductive proof scheme, specific to the considered problem and graph class, where arguing the validity of the scheme is rarely immediate. We use variants of the discharging method to study two types of coloring problems.

Cette thèse concerne l'étude de l'algorithmique et de la complexité des communications dans les réseaux radio. En particulier, nous nous sommes intéressés au problème de rassembler les informations des sommets d'un réseau radio en un noeud central.<br />Ce problème est motivé par une question de France Telecom (Orange Labs) "comment amener Internet dans les villages".<br />Les sommets représentent les maisons des villages qui communiquent entre elles par radio, le but étant d'atteindre une passerelle centrale connectée à Internet par une liaison satellite. Le même problème se rencontre dans les réseaux de senseurs où il s'agit de collecter les informations des senseurs dans une station de base.<br />Une particularité des réseaux radio est que la distance de transmission est limité et que les transmissions interfèrent entre elles (phénomènes d'interférences). Nous modélisons ces contraintes en disant que deux sommets (équipements radio) peuvent communiquer s'ils sont à distance au plus dT et qu'un noeud interfère avec un autre si leur distance est au plus dI. Les distances sont considérées dans un graphe représentant le réseau. Une étape de communication consistera donc en un ensemble de transmissions compatibles (n'interférant pas).<br />Notre objectif est de trouver le nombre minimum d'étapes nécessaires pour réaliser un tel rassemblement et de concevoir des algorithmes réalisant ce minimum. Pour des topologies particulières comme le chemin et la grille, nous avons établi des résultats optimaux ou quasi optimaux.<br />Nous avons aussi considéré le cas systolique (ou continu) où on veut maximiser le debit offert à chaque noeud.

Étude sur les graphes bipartis orientes de Moore montrant que de tels graphes existent, pour certaines valeurs du diamètre, et servent a la construction d'une classe de graphes bipartis orientes, asymptotiquement optimaux. Dans la deuxième partie du travail, quelques notions de coloration des graphes sont présentées. Celles-ci permettent de généraliser certains résultats déjà connus dans le cadre de la coloration habituelle et d'en obtenir d'autres plutôt spécifiques a ces notions. La généralisation de la notion de perfection en b-perfection est proposée ce qui permet l'obtention des graphes triangules représentant la seule classe de graphes b-parfaits

Many Hymenoptera, with their painful stings and noxious chemical defenses, exhibit bright aposematic warning color patterns and are the most frequently mimicked group of organisms. Such aposematic color patterns are found in parasitic wasps of the Neotropical Compsobracon group (Braconidae). Many members of this group exhibit color patterns similar to several thousand other species of Braconidae, Ichneumonidae, sawflies, assassin bugs, flies, moths, and beetles. One hypothesis to explain this observation is that the members of the complex and their colors are generated by multiple cospeciation events resulting in the constituent genera having isomorphic phylogenetic trees. An alternative hypothesis is that the organisms have colonized existing color pattern niches independently and do not have topologically similar phylogenetic histories. In order to test the hypothesis that these patterns are the result of cospeciation events they will be described and mapped onto a phylogenetic tree. If clades are found to have isomorphic topologies; evidence will suggest cospeciation. However, if clades are not found to have similar topologies, evidence will suggest independent colonization of color pattern niches. / Graduation date: 2006

A prey animal can use different strategies to avoid becoming eaten by predators. One such widely recognised strategy is the use of body colouration to decrease the risk of becoming detected, i.e. cryptic colouration. The principles of crypsis that I have studied are background matching, disruptive colouration and distractive markings. Further, I also studied the concealing effect of the visual background habitats. I used artificial prey items and backgrounds, and blue tits (Cyanistes caeruleus) as predators, to investigate prey concealment. In Paper I, I tested if high-contrast markings in prey coloration or in the background would result in a distracting effect. I found that such markings did increase prey search time, even when the prey markings were lighter or darker than the background. In Paper II, I studied the use of chromatic cues by predators when searching for prey. The birds easily detected prey that chromatically deviated from its background. Interestingly, background-matching prey was more difficult to detect when the colour scheme had low ultraviolet and high shortwave reflectance compared to when the reflectance bands were even. In Paper III, I studied optimisation of achromatic contrast within prey colour pattern and also the effect of shape diversity of background pattern elements on prey detection. I found that all prey types were more difficult to detect on the diverse background, but the level of contrast within prey pattern did not influence search times. In Paper IV, I further investigated how a prey should optimise its patterning with respect to background matching. I found that prey with repeated pattern elements was equally hard to detect as prey with more variable pattern. However, prey with a spatially regular pattern (aligned pattern elements) was easier to detect than prey with a spatially irregular pattern. In this paper I also found that high complexity of element shapes in the background, made the search task more difficult. / At the time of the doctoral defense, the following papers were unpublished and had a status as follows: Paper 1: Manuscript. Paper 2: Accepted

Dans cette thèse nous étudions différents problèmes de graphes et multigraphes arêtes-coloriés tels que la connexité propre, la coloration forte d'arêtes et les chaînes et cycles hamiltoniens propres. Enfin, nous améliorons l'algorithme connu $O(n^4)$ pour décider du comportement d'un graphe sous opérateur biclique, en étudiant les bicliques dans les graphes sans faux jumeaux. Plus précisément, 1) Nous étudions d'abord le nombre $k$-connexité-propre des graphes, noté $pc_k(G)$, ç'est à dire le nombre minimum de couleurs nécessaires pour colorer les arêtes d'un graphe de façon à ce qu'entre chaque paire de sommets, ils existent $k$ chemins intérieurement sommet-disjoints. Nous prouvons plusieurs bornes supérieures pour $pc_k(G)$. Nous énonçons quelques conjectures pour les graphes généraux et bipartis et nous les prouvons dans le cas où $k = 1$. 2) Nous étudions l'existence de chaînes et de cycles hamiltoniens propres dans les multigraphes arêtes-coloriés. Nous établissons des conditions suffisantes, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré arc-en-ciel, la connexité, etc. 3) Nous montrons que l'indice chromatique fort est linéaire au degré maximum pour tout graphe $k$-dégénéré où, $k$ est fixe. En corollaire, notre résultat conduit à une amélioration des constantes et donne également un algorithme plus simple et plus efficace pour cette famille de graphes. De plus, nous considérons les graphes planaires extérieurs. Nous donnons une formule pour trouver l'indice chromatique fort exact pour les graphes bipartis planaires extérieurs. Nous améliorons également la borne supérieure pour les graphes planaires extérieurs généraux. 4) Enfin, nous étudions les bicliques dans les graphes sans faux jumeaux et nous présentons ensuite un algorithme $O(n+m)$ pour reconnaître les graphes convergents et divergents en améliorant l'algorithme $O(n^4)$.

Hermaphroditism, associated with territoriality and dominance behavior, is common in the marine environment. Male sex-specific coloration patterns and behavior are particularly evident in species where males are territorial and guard harems of females such as wrasses and groupers. Protogynous hermaphrodites that change sex from female to male are good models to study sexual behavior and related changes in the brain due to their abilities to reorganize their sexual phenotype as adults. Two hormones produced in the brain and implicated in the process of sex-specific behavior and reproductive development are arginine vasotocin (AVT) and gonadotropin releasing hormone (GnRH). While a wealth of data exists regarding these hormone systems separately, little is known about linkage between these two systems. Especially there is no data tracking these two systems together in any protogynous fish. This study was conducted to test the hypothesis that coordinated interactions between AVT and GnRH facilitate the process of behavioral and gonadal sex change in the rock hind Epinephelus adscensionis. Four topics were addressed to investigate the relationship between behavior and reproduction: i) rock hind sex change, sexual characteristics and conditions causing sex change to occur in captivity were detailed as a basis for examining the AVT system and GnRH during this process, ii) the distribution of a vasotocin V1a type receptor identified in rock hind brain was examined for the first time in a fish species using a custom designed antibody then the receptor protein was co-localized with GnRH producing cells within the brain to confirm that a pathway exists for AVT action on GnRH, iii) levels of AVT, AVT receptors, and GnRH messenger RNA (mRNA) were compared between male and female rock hind phenotypes, and iv) female rock hind at early stages of sex change were compared for brain mRNA expression of AVT, AVT receptors, and GnRH to determine the order of hormonal change during the process of sexual inversion in this species. This study provides a better understanding of the relationship between sex-specific behavior and reproductive development via AVT and GnRH systems that are conserved in all vertebrates. / text

Ce manuscrit d'Habilitation à diriger des recherches décrit mes travaux de recherche récents en théorie des graphes et en théorie des jeux combinatoires. Une première partie est consacrée à l'étude de paramètres de graphes en s'intéressant particulièrement aux contraintes structurelles qui permettent d'améliorer les bornes connues. Dans cette partie, nous traitons notamment la paire-domination, la domination indépendante mais aussi les partitions en cographes et les colorations quasi propres. Une deuxième partie traite de la domination de puissance, une forme itérative de la domination au sujet de laquelle nous proposons un début de synthèse des résultats existants. Enfin, une troisème partie parle de jeux. Nous y traitons d'abord le travail réalisé sur quelques conjectures portant sur un jeu de domino, puis au sujet des jeux en version misère. Nous y parlons enfin du jeu de domination, qui est à l'interface entre le paramètre de graphe et le jeu combinatoire.

This thesis investigates the possibility of using aposematic insects as guides to plants that contain pharmacologically-active compounds. Plants were monitored within national parks in the Republic of Panama over a period of six months and all insects feeding on them were collected and raised in captivity. The insects were then extracted and analyzed to determine how they were treating toxic chemical compounds in their host plant. Two principal plants were investigated with their associated insects: (1) Vismia baccifera and (2) Mikania guaco. One generalist and one specialist Lepidopteran species were found to sequester vismione B from their host plant Vismia baccifera, a cytotoxic compound active against three cancer cell lines. Two specialist Coleopterans were found to sequester the novel compound Guacanone, isolated by the primary author from the vine Mikania guaco and active against Trypanosoma cruzi, the causative agent of Chagas' disease. A generalist Coleopteran was found to not sequester this compound. (Abstract shortened by UMI.)

Les machines du domaine du calcul haute performance (HPC) gagnent régulièrement en com- plexité. De nos jours, chaque nœud de calcul peut être constitué de plusieurs puces ou de plusieurs cœurs se partageant divers caches mémoire de façon hiérarchique. Que se soit pour comprendre les performances ob- tenues par une application sur ces architectures ou pour développer de nouveaux algorithmes et valider leur performance, une phase d'expérimentation est souvent nécessaire. Dans cette thèse, nous nous intéressons à deux formes d'analyse expérimentale : l'exécution sur machines réelles et la simulation d'algorithmes sur des jeux de données aléatoires. Dans un cas comme dans l'autre, le contrôle des paramètres de l'environnement (matériel ou données en entrée) permet une meilleure analyse des performances de l'application étudiée. Ainsi, nous proposons deux méthodes pour contrôler l'utilisation par une application des ressources ma- térielles d'une machine : l'une pour le temps processeur alloué et l'autre pour la quantité de cache mémoire disponible. Ces deux méthodes nous permettent notamment d'étudier les changements de comportement d'une application en fonction de la quantité de ressources allouées. Basées sur une modification du compor- tement du système d'exploitation, nous avons implémenté ces méthodes pour un système Linux et démontré leur utilité dans l'analyse de plusieurs applications parallèles. Du point de vue de la simulation, nous avons étudié le problème de la génération aléatoire de graphes orientés acycliques (DAG) pour la simulation d'algorithmes d'ordonnancement. Bien qu'un grand nombre d'algorithmes de génération existent dans ce domaine, la plupart des publications repose sur des implémen- tations ad-hoc et peu validées de ces derniers. Pour pallier ce problème, nous proposons un environnement de génération comprenant la majorité des méthodes rencontrées dans la littérature. Pour valider cet envi- ronnement, nous avons réalisé de grande campagnes d'analyses à l'aide de Grid'5000, notamment du point de vue des propriétés statistiques connues de certaines méthodes. Nous montrons aussi que la performance d'un algorithme est fortement influencée par la méthode de génération des entrées choisie, au point de ren- contrer des phénomènes d'inversion : un changement d'algorithme de génération inverse le résultat d'une comparaison entre deux ordonnanceurs.