• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 75
  • 54
  • 15
  • 11
  • 8
  • 3
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • Tagged with
  • 179
  • 43
  • 40
  • 36
  • 33
  • 32
  • 32
  • 16
  • 15
  • 14
  • 14
  • 14
  • 13
  • 13
  • 13
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
31

Colorations de graphes sous contraintes / Graph coloring under constraints

Hocquard, Hervé 05 December 2011 (has links)
Dans cette thèse, nous nous intéressons à différentes notions de colorations sous contraintes. Nous nous intéressons plus spécialement à la coloration acyclique, à la coloration forte d'arêtes et à la coloration d'arêtes sommets adjacents distinguants.Dans le Chapitre 2, nous avons étudié la coloration acyclique. Tout d'abord nous avons cherché à borner le nombre chromatique acyclique pour la classe des graphes de degré maximum borné. Ensuite nous nous sommes attardés sur la coloration acyclique par listes. La notion de coloration acyclique par liste des graphes planaires a été introduite par Borodin, Fon-Der Flaass, Kostochka, Raspaud et Sopena. Ils ont conjecturé que tout graphe planaire est acycliquement 5-liste coloriable. De notre côté, nous avons proposé des conditions suffisantes de 3-liste coloration acyclique des graphes planaires. Dans le Chapitre 3, nous avons étudié la coloration forte d'arêtes des graphes subcubiques en majorant l'indice chromatique fort en fonction du degré moyen maximum. Nous nous sommes également intéressés à la coloration forte d'arêtes des graphes subcubiques sans cycles de longueurs données et nous avons également obtenu une majoration optimale de l'indice chromatique fort pour la famille des graphes planaires extérieurs. Nous avons aussi présenté différents résultats de complexité pour la classe des graphes planaires subcubiques. Enfin, au Chapitre 4, nous avons abordé la coloration d'arêtes sommets adjacents distinguants en déterminant les majorations de l'indice avd-chromatique en fonction du degré moyen maximum. Notre travail s'inscrit dans la continuité de celui effectué par Wang et Wang en 2010. Plus précisément, nous nous sommes focalisés sur la famille des graphes de degré maximum au moins 5. / In this thesis, we are interested in various coloring of graphs under constraints. We study acyclic coloring, strong edge coloring and adjacent vertex-distinguishing edge coloring.In Chapter 2, we consider acyclic coloring and we bound the acyclic chromatic number by a function of the maximum degree of the graph. We also study acyclic list coloring. The notion of acyclic list coloring of planar graphs was introduced by Borodin, Fon-Der Flaass, Kostochka, Raspaud, and Sopena. They conjectured that every planar graph is acyclically 5-choosable. We obtain some sufficient conditions for planar graphs to be acyclically 3-choosable.In Chapter 3, we study strong edge coloring of graphs. We prove some upper bounds of the strong chromatic index of subcubic graphs as a function of the maximum average degree. We also obtain a tight upper bound for the minimum number of colors in a strong edge coloring of outerplanar graphs as a function of the maximum degree. We also prove that the strong edge k-colouring problem, when k=4,5,6, is NP-complete for subcubic planar bipartite graphs with some girth condition. Finally, in Chapter 4, we focus on adjacent vertex-distinguishing edge coloring, or avd-coloring, of graphs. We bound the avd-chromatic number of graphs by a function of the maximum average degree. This work completes a result of Wang and Wang in 2010.
32

Sélection sexuelle et les traits des femelles : la mésange bleue comme modèle d'étude / Sexual selection and female signals : blue tits as study model

Midamegbe, Afiwa 16 December 2010 (has links)
Chez les espèces où mâles et femelles portent des traits voyants et élaborés, les traits observés chez les femelles peuvent être des sous-produits non-fonctionnels de la sélection sexuelle exercée sur les traits mâles ou alors être directement soumis à la sélection. Cette thèse a eu pour objectif de tester l'hypothèse de sélection sexuelle chez les femelles de Mésange bleue (Cyanistes caeruleus) sur trois traits présents chez le mâle et la femelle : (1) la coloration structurelle UV/bleue de la tête, (2) la coloration jaune basée sur les caroténoïdes de la poitrine et (3) l'agressivité. Pour cela, nous avons testé expérimentalement (1) le lien entre les traits colorés et le transfert de composants potentiellement bénéfiques dans les ufs, (2) la condition-dépendance des traits colorés, (3) l'utilisation de la coloration du plumage dans les interactions femelle-femelle et (4) le lien entre l'agressivité des femelles et leur investissement dans la reproduction. Enfin, nous avons exploré le rôle potentiel des couleurs femelles dans le choix de partenaires mâle en testant le lien entre la couleur UV/bleue des femelles et le nombre de jeunes issus de copulations hors couple et l'appariement selon la couleur bleue et jaune dans notre population. Nos résultats suggèrent (1) qu'il existe un lien entre la qualité maternelle et la coloration de leur plumage, (2) que les couleurs UV/bleues et jaune du plumage sont conditions-dépendants, (3) que les UV/bleus de la tête sont utilisés comme badge de statut dans les interactions femelle-femelle, (4) qu'il pourrait exister un compromis entre l'agressivité femelle et son investissement dans la reproduction et (5) qu'il existe un potentiel choix mutuel de partenaires basés sur les couleurs. Au final, cette thèse a ainsi permis de mettre en évidence que chez une espèce où mâles et femelles sont ornementés, les traits colorés femelles ont le potentiel d'évoluer sous l'effet direct de la sélection sexuelle. / In mutually ornamented species, female conspicuous traits could be non-functional by-products of sexual selection acting on male traits or could be directly under selection. The aim of this PhD was to test the hypothesis of sexual selection in Blue tit (Cyanistes caeruleus) females on three traits present in both males and females: (1) the structural coloration of the UV/blue crown, (2) the yellow chest coloration based on carotenoids and (3) aggressiveness. To do so, we experimentally tested (1) the links between plumage coloration and the transfer of potentially beneficial components in egg yolks, (2) the condition-dependence of the plumage coloration, (3) the use of the plumage coloration in female-female interactions and (4) the link between female aggressiveness and investment in reproduction. Finally, we explored the role of female plumage coloration in male mate choice by testing the link between female UV/blue crown coloration and the n umber of extra-pair young in the nest and by estimating whether the individuals were assortatively mated in respect of their yellow and blue coloration in the studied population. Our results suggest that (1) there is a link between female plumage coloration and maternal quality, (2) plumage UV/blue and yellow coloration is condition-dependant, (3) the UV/blue crown is used as a badge of status in female-female interactions, (4) there could be a trade-off between female aggressiveness and female investment in reproduction and (5) there is a potential mutual mate choice based on both coloration. So, this PhD supports the hypothesis that in a mutually ornamented species, female ornaments are potentially under direct sexual selection.
33

Hybrid metaheuristic algorithms for sum coloring and bandwidth coloring / Métaheuristiques hybrides pour la somme coloration et la coloration de bande passante

Jin, Yan 29 May 2015 (has links)
Le problème de somme coloration minimum (MSCP) et le problème de coloration de bande passante (BCP) sont deux généralisations importantes du problème de coloration des sommets classique avec de nombreuses applications dans divers domaines, y compris la conception de circuits imprimés, la planication, l’allocation de ressource, l’affectation de fréquence dans les réseaux mobiles, etc. Les problèmes MSCP et BCP étant NP-difficiles, les heuristiques et métaheuristiques sont souvent utilisées en pratique pour obtenir des solutions de bonne qualité en un temps de calcul acceptable. Cette thèse est consacrée à des métaheuristiques hybrides pour la résolution efcace des problèmes MSCP et BCP. Pour le problème MSCP, nous présentons deux algorithmes mémétiques qui combinent l’évolution d’une population d’individus avec de la recherche locale. Pour le problème BCP, nous proposons un algorithme hybride à base d’apprentissage faisant coopérer une méthode de construction “informée” avec une procédure de recherche locale. Les algorithmes développés sont évalués sur des instances biens connues et se révèlent très compétitifs par rapport à l’état de l’art. Les principaux composants des algorithmes que nous proposons sont également analysés. / The minimum sum coloring problem (MSCP) and the bandwidth coloring problem (BCP) are two important generalizations of the classical vertex coloring problem with numerous applications in diverse domains, including VLSI design, scheduling, resource allocation and frequency assignment in mobile networks, etc. Since the MSCP and BCP are NP-hard problems, heuristics and metaheuristics are practical solution methods to obtain high quality solutions in an acceptable computing time. This thesis is dedicated to developing effective hybrid metaheuristic algorithms for the MSCP and BCP. For the MSCP, we present two memetic algorithms which combine population-based evolutionary search and local search. An effective algorithm for maximum independent set is devised for generating initial solutions. For the BCP, we propose a learning-based hybrid search algorithm which follows a cooperative framework between an informed construction procedure and a local search heuristic. The proposed algorithms are evaluated on well-known benchmark instances and show highly competitive performances compared to the current state-of-the-art algorithms from the literature. Furthermore, the key issues of these algorithms are investigated and analyzed.
34

Colorations de graphes et applications

Sereni, Jean-Sébastien 05 July 2006 (has links) (PDF)
Cette thèse comporte trois parties. Dans la première partie, un problème d'allocation de fréquences, proposé par Alcatel, est modélisé en termes de coloration de graphes : un graphe est k-improprement l-colorable<br />s'il est possible, étant données l couleurs, d'attribuer une couleur à chacun de ses sommets de sorte que chaque sommet ait au plus k voisins de la même couleur que lui.<br />Différentes problématiques sont ensuite étudiées :<br />la coloration impropre (et la choisissabilité impropre) des<br />graphes de densité bornée (englobant le cas des graphes de genre borné et de maille donnée), celles des graphes d'intersection de disques unitaires (y compris<br />pour des instances aléatoires, et pour des ensembles de points infinis), ainsi que la coloration impropre pondérée des sous-graphes du réseau triangulaire.<br /><br />La deuxième partie regroupe différents problèmes de colorations de graphes, plus ou moins reliés au problème d'allocation de fréquences, pour lesquels nous avons obtenus de nouveaux résultats. Il s'agit de la coloration 3-faciale des graphes planaires, de la choisissabilité circulaire et de diverses généralisations de l'arête-coloration des graphes cubiques, en particulier par des éléments de groupes abéliens, et des triplets de Steiner.<br /><br />Dans la troisième partie, nous nous intéressons à un problème de reroutage de requêtes, sans perte de service, dans les réseaux WDM. Dans un premier temps, un nouvel invariant des graphes est introduit afin de modéliser cette question.<br />Comme il s'avère que ce paramètre est proche de celui, bien connu, de largeur arborescente linéaire (pathwidth), ce dernier nous a également intéressé et nous avons<br />obtenu de nouveaux résultats concernant la relation entre la largeur arborescente lineaire d'un graphe planaire extérieur 2-connexe et celle de son dual.
35

Coloration de graphes : structures et algorithmes

Lévêque, Benjamin 15 October 2007 (has links) (PDF)
De nombreux problèmes appliqués peuvent être modélisés par le problème de la coloration des sommets d'un graphe, qui est NP-complet en général mais polynomial sur la classe des graphes parfaits introduite par Berge. L'algorithme de coloration des graphes parfaits, de Grötschel, Lovasz et Schrijver, n'est pas réellement efficace d'un point de vue pratique et il est toujours intéressant de trouver un algorithme ''purement'' combinatoire permettant de colorier les graphes parfaits en temps polynomial. Dans cette thèse, nous donnons plusieurs algorithmes simples et rapides permettant de colorier des sous-classes de graphes parfaits. Ces algorithmes utilisent en particulier la notion de contraction de paire d'amis, introduite par Fonlupt et Uhry, à propos de laquelle plusieurs conjectures sont encore ouvertes. Nous utilisons aussi des algorithmes de parcours comme LexBFS, de Rose, Tarjan et Lueker, pour prouver des résultats structuraux sur les graphes considérés.
36

Problèmes de clique maximum avec applications à la coloration de graphe

Wu, Qinghua 19 February 2013 (has links) (PDF)
Le problème de la clique maximum (MCP) est un problème d'optimisation combinatoire important avec un large éventail d'applications pratiques dans de nombreux domaines, y compris la recherche d'information, l'analyse de la transmission du signal, la théorie de la classification, l'économie, la planification et l'ingénierie biomédicale. En outre, un certain nombre de problèmes d'optimisation combinatoire sont étroitement liés au MCP, tels que la coloration de graphe, la somme coloration, réglez détermination du gagnant emballage et optimale. Cette thèse est consacrée à l'élaboration d'approches heuristiques efficaces pour s'attaquer au problème de la clique maximum et ses généralisations. Pour atteindre cet objectif, nous avons développé une approche de recherche tabou adaptative multistart pour le problème de clique maximum classique, un algorithme recherche tabou multi-voisinage pour la clique maximum de sommets pondérés, et une méthode métaheuristique hybride pour le problème de la clique maximum d'arêtes pondérés. En outre, nous appliquons ces méthodes heuristiques développées pour résoudre ces problèmes difficiles qui sont étroitement liés au problème de la clique maximum. Tous les algorithmes sont mis en oeuvre et testés avec succès sur un certain nombre de cas de référence provenant de divers domaines d'application. Les méthodes proposées concurrencent favorablement les autres approches de l'état de l'art.
37

Coloration, ensemble indépendant et structure de graphe / Coloring, stable set and structure of graphs

Pastor, Lucas 23 November 2017 (has links)
Cette thèse traite de la coloration de graphe, de la coloration par liste,d'ensembles indépendants de poids maximum et de la théorie structurelle des graphes.Dans un premier temps, nous fournissons un algorithme s'exécutant en temps polynomial pour le problème de la 4-coloration dans des sous-classes de graphe sans $P_6$. Ces algorithmes se basent sur une compréhension précise de la structure de ces classes de graphes, pour laquelle nous donnons une description complète.Deuxièmement, nous étudions une conjecture portant sur la coloration par liste et prouvons que pour tout graphe parfait sans griffe dont la taille de la plus grande clique est bornée par 4, le nombre chromatique est égal au nombre chromatique par liste. Ce résultat est obtenu en utilisant un théorème de décomposition des graphes parfaits sans griffe, une description structurelle des graphes de base de cette décomposition et le célèbre théorème de Galvin.Ensuite, en utilisant la description structurelle élaborée dans le premier chapitre et en renforçant certains aspects de celle-ci, nous fournissons un algorithme s'exécutant en temps polynomial pour le problème d'indépendant de poids maximum dans des sous-classes de graphe sans $P_6$ et sans $P_7$. Dans le dernier chapitre de ce manuscrit, nous infirmons une conjecture datant de 1999 de De Simone et K"orner sur les graphes normaux. Notre preuve est probabiliste et est obtenue en utilisant les graphes aléatoires. / This thesis deals with graph coloring, list-coloring, maximum weightstable set (shortened as MWSS) and structural graph theory.First, we provide polynomial-time algorithms for the 4-coloring problem insubclasses of $P_6$-free graphs. These algorithms rely on a preciseunderstanding of the structure of these classes of graphs for which we give afull description.Secondly, we study the list-coloring conjecture and prove that for anyclaw-free perfect graph with clique number bounded by 4, the chromatic numberand the choice number are equal. This result is obtained by using adecomposition theorem for claw-free perfect graphs, a structural description ofthe basic graphs of this decomposition and by using Galvin's famous theorem.Next by using the structural description given in the first chapter andstrengthening other aspects of this structure, we provide polynomial-timealgorithms for the MWSS problem in subclasses of $P_6$-free and $P_7$-freegraphs.In the last chapter of the manuscript, we disprove a conjecture of De Simoneand K"orner made in 1999 related to normal graphs. Our proof is probabilisticand is obtained by the use of random graphs.
38

Cycles in graphs and arc colorings in digraphs / Cycles des graphes et colorations d’arcs des digraphes

He, Weihua 28 November 2014 (has links)
Dans cette thèse nous étudions quatre problèmes de théorie des graphes. En particulier,Nous étudions le problème du cycle hamiltonien dans les line graphes, et aussi nous prouvons l’existence de cycles hamiltoniens dans certains sous graphes couvrants d’un line graphe. Notre résultat principal est: Si L(G) est hamiltonien, alors SL(G) est hamiltonien. Grâce à ce résultat nous proposons une conjecture équivalente à des conjectures célèbres. Et nous obtenons deux résultats sur les cycles hamiltoniens disjoints dans les line graphes.Nous considérons alors la bipancyclicité résistante aux pannes des graphes de Cayley engendrés par transposition d’arbres. Nous prouvons que de tels graphes de Cayley excepté le “star graph” ont une bipancyclicité (n − 3)-arête résistante aux pannes.Ensuite nous introduisons la coloration des arcs d’un digraphe sommet distinguant. Nous étudions la relation entre cette notion et la coloration d’arêtes sommet distinguant dans les graphes non orientés. Nous obtenons quelques résultats sur le nombre arc chromatique des graphes orientés (semi-)sommet-distinguant et proposons une conjecture sur ce paramètre. Pour vérifier cette conjecture nous étudions la coloration des arcs d’un digraphe sommet distinguant des graphes orientés réguliers.Finalement nous introduisons la coloration acyclique des arcs d’un graphe orienté. Nous calculons le nombre chromatique acyclique des arcs de quelques familles de graphes orientés et proposons une conjecture sur ce paramètre. Nous considérons les graphes orientés de grande maille et utilisons le Lemme Local de Lovász; d’autre part nous considérons les graphes orientés réguliers aléatoires. Nous prouvons que ces deux classes de graphes vérifient la conjecture. / In this thesis, we study four problems in graph theory, the Hamiltonian cycle problem in line graphs, the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees, the vertex-distinguishing arc colorings in digraph- s and the acyclic arc coloring in digraphs. The first two problems are the classic problem on the cycles in graphs. And the other two arc coloring problems are related to the modern graph theory, in which we use some probabilistic methods. In particular,We first study the Hamiltonian cycle problem in line graphs and find the Hamiltonian cycles in some spanning subgraphs of line graphs SL(G). We prove that: if L(G) is Hamiltonian, then SL(G) is Hamiltonian. Due to this, we propose a conjecture, which is equivalent to some well-known conjectures. And we get two results about the edge-disjoint Hamiltonian cycles in line graphs.Then, we consider the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees. And we prove that the Cayley graph generated by transposition tree is (n − 3)-edge-fault-tolerant bipancyclic if it is not a star graph.Later, we introduce the vertex-distinguishing arc coloring in digraphs. We study the relationship between the vertex-distinguishing edge coloring in undirected graphs and the vertex-distinguishing arc coloring in digraphs. And we get some results on the (semi-) vertex-distinguishing arc chromatic number for digraphs and also propose a conjecture about it. To verify the conjecture we study the vertex-distinguishing arc coloring for regular digraphs.Finally, we introduce the acyclic arc coloring in digraphs. We calculate the acyclic arc chromatic number for some digraph families and propose a conjecture on the acyclic arc chromatic number. Then we consider the digraphs with high girth by using the Lovász Local Lemma and we also consider the random regular digraphs. And the results of the digraphs with high girth and the random regular digraphs verify the conjecture.
39

Quelques problèmes de coloration du graphe / Some coloring problems of graphs

Xu, Renyu 27 May 2017 (has links)
Un k-coloriage total d'un graphe G est un coloriage de V(G)cup E(G) utilisant (1,2,…,k) couleurs tel qu'aucune paire d'éléments adjacents ou incidents ne reçoivent la même couleur. Le nombre chromatique total chi''(G) est le plus petit entier k tel que G admette un k-coloriage total. Dans le chapitre 2, nous étudions la coloration totale de graphe planaires et obtenons 3 résultats : (1) Soit G un graphe planaire avec pour degré maximum Deltageq8. Si toutes les paires de 6-cycles cordaux ne sont pas adjacentes dans G, alors chi''(G)=Delta+1. (2) Soit G un graphe planaire avec pour degré maximum Deltageq8. Si tout 7-cycle de G contient au plus deux cordes, alors chi''(G)=Delta+1. (3) Soit G un graphe planaire sans 5-cycles cordaux qui s'intersectent, c'est à dire tel que tout sommet ne soit incident qu'à au plus un seul 5-cycle cordal. Si Deltageq7, alors chi''(G)=Delta+1.Une relation L est appelé assignation pour un graphe G s'il met en relation chaque x à une liste de couleur. S'il est possible de colorier G tel que la couleur de chaque x soit présente dans la liste qu'il lui a été assignée, et qu'aucune paire de sommets adjacents n'aient la même couleur, alors on dit que G est L-coloriable. Un graphe G est k-selectionable si G est L-coloriable pour toute assignation L de G qui satisfait |L(v)geq k| pour tout x. Nous démontrons que si chaque 5-cycle de G n'est pas simultanément adjacent à des 3-cycles et des 4-cycles, alors G est 4-sélectionable. Dans le chapitre 3, nous prouvons que si aucun des 5-cycles de G n'est adjacent à un 4-cycles, alors chi'_l(G)=Delta et chi''_l(G)=Delta+1 si Delta(G)geq8, et chi'_l(G)leqDelta+1 et chi''_l(G)leqDelta+2 si Delta(G)geq6.Dans le chapitre 4, nous allons fournir une définition du coloriage total somme-des-voisins-distinguant, et passer en revue les progrgrave{e}s et conjecture concernant ce type de coloriage. Soit f(v) la somme des couleurs d'un sommet v et des toutes les arrêtes incidentes à v. Un k-coloriage total somme-des-voisins-distinguant de G est un k coloriage total de G tel que pour chaque arrête uvin E(G), f(u)eq f(v). Le plus petit k tel qu'on ai un tel coloriage sur G est appelé le nombre chromatique total somme-des-voisins-distinguant, noté chi''_{sum} (G). Nous avons démontré que si un graphe G avec degré maximum Delta(G) peut être embedded dans une surface Sigma de caractéristique eulérienne chi(Sigma)geq0, alors chi_{sum}^{''}(G)leq max{Delta(G)+2, 16}.Une forêt linéaire est un graphe pour lequel chaque composante connexe est une chemin. L'arboricité linéaire la(G) d'un graphe G tel que définie est le nombre minimum de forêts linéaires dans G, dont l'union est égale à V(G). Dans le chapitre 5, nous prouvons que si G est une graphe planaire tel que tout 7-cycle de G contienne au plus deux cordes, alors G est linéairementleft lceil frac{Delta+1}{2}ightceil-sélectionable si Delta(G)geq6, et G est linéairement left lceil frac{Delta}{2}ightceil-sélectionable si Delta(G)geq 11. / A k-total-coloring of a graph G is a coloring of V(G)cup E(G) using (1,2,…,k) colors such that no two adjacent or incident elements receive the same color.The total chromatic number chi''(G) is the smallest integer k such that G has a k-total-coloring. In chapter 2, we study total coloring of planar graphs and obtain three results: (1) Let G be a planar graph with maximum degree Deltageq8. If every two chordal 6-cycles are not adjacent in G, then chi''(G)=Delta+1. (2) Let G be a planar graph G with maximum degree Deltageq8. If any 7-cycle of G contains at most two chords, then chi''(G)=Delta+1. (3) Let G be a planar graph without intersecting chordal 5-cycles, that is, every vertex is incident with at most one chordal 5-cycle. If Deltageq7, then chi''(G)=Delta+1.A mapping L is said to be an assignment for a graph G if it assigns a list L(x) of colors to each xin V(G)cup E(G). If it is possible to color G so that every vertex gets a color from its list and no two adjacent vertices receive the same color, then we say that G is L-colorable. A graph G is k-choosable if G is an L-colorable for any assignment L for G satisfying |L(x)|geq k for every vertex xin V(G)cup E(G). We prove that if every 5-cycle of G is not simultaneously adjacent to 3-cycles and 4-cycles, then G is 4-choosable. In chapter 3, if every 5-cycles of G is not adjacent to 4-cycles, we prove that chi'_l(G)=Delta, chi''_l(G)=Delta+1 if Delta(G)geq8, and chi'_l(G)leqDelta+1, chi''_l(G)leqDelta+2 if Delta(G)geq6.In chapter 4, we will give the definition of neighbor sum distinguishing total coloring. Let f(v) denote the sum of the colors of a vertex v and the colors of all incident edges of v. A total k-neighbor sum distinguishing-coloring of G is a total k-coloring of G such that for each edge uvin E(G), f(u)eq f(v). The smallestnumber k is called the neighbor sum distinguishing total chromatic number, denoted by chi''_{sum} (G). Pilsniak and Wozniak conjectured that for any graph G with maximum degree Delta(G) holds that chi''_{sum} (G)leqDelta(G)+3. We prove for a graph G with maximum degree Delta(G) which can be embedded in a surface Sigma of Euler characteristic chi(Sigma)geq0, then chi_{sum}^{''}(G)leq max{Delta(G)+2, 16}.Lastly, we study the linear L-choosable arboricity of graph. A linear forest is a graph in which each component is a path. The linear arboricity la(G) of a graph G is the minimum number of linear forests in G, whose union is the set of all edges of G. A list assignment L to the edges of G is the assignment of a set L(e)subseteq N of colors to every edge e of G, where N is the set of positive integers. If G has a coloring varphi (e) such that varphi (e)in L(e) for every edge e and (V(G),varphi^{-1}(i)) is a linear forest for any iin C_{varphi}, where C_{varphi }=left { varphi (e)|ein E(G)ight }, then we say that G is linear L-colorable and varphi is a linear L-coloring of G. We say that G is linear k-choosable if it is linear L-colorable for every list assignment L satisfying |L(e)| geq k for all edges e. The list linear arboricity la_{list}(G) of a graph G is the minimum number k for which G is linear k-list colorable. It is obvious that la(G)leq la_{list}(G). In chapter 5, we prove that if G is a planar graph such that every 7-cycle of G contains at most two chords, then G is linear left lceil frac{Delta+1}{2}ightceil-choosable if Delta(G)geq6, and G is linear left lceil frac{Delta}{2}ightceil-choosable if Delta(G)geq 11.
40

Influence de l'iridescence sur le succès reproducteur des mâles Hirondelle bicolore (Tachycineta bicolor)

Van Wijk, Sonia January 2015 (has links)
En élaborant la théorie de la sélection sexuelle, Darwin a levé le voile sur les causes de l’évolution de traits extravagants plus souvent observés chez les mâles, comme la coloration du plumage chez les oiseaux. Un des mécanismes proposés pour expliquer l’évolution des couleurs vives chez les mâles est la fonction de signal de condition. Les mâles pourraient donc être préférés par les femelles puisque celles-ci obtiendraient des bénéfices directs, comme un meilleur territoire, ou des bénéfices indirects, tels que de bons gènes pour leurs oisillons. La sélection sexuelle de l’iridescence, un mode de coloration répandu chez les oiseaux, est encore peu documentée à ce jour. L’iridescence est un mécanisme de coloration directionnel, c’est-à-dire qu’il occasionne un changement de brillance avec un mouvement de l’animal. Cette propriété unique à l’iridescence amène une difficulté de quantification qui a longtemps limité son étude. Le but de mon projet était donc, dans un premier temps, de fabriquer un appareil de mesure répétable de l’iridescence déjà publié dans la littérature afin de le tester chez l’Hirondelle bicolore (Tachycineta bicolor). Dans un deuxième temps, j’ai vérifié si l’iridescence des mâles Hirondelle bicolore (Tachycineta bicolor) influençait leur succès reproducteur. Grâce à l’appareil de mesure, j’ai pu montrer qu’il y avait des différences individuelles dans la directionnalité de l’iridescence. De plus, j’ai pu établir que ces différences étaient reliées au nombre de jeunes dans le couple du mâle. Cette variable, pour la première fois associée au succès reproducteur, pourrait jouer un rôle dans le signalement de la capacité à donner des soins parentaux. De plus, les mâles brillants avaient un avantage pour les paternités hors couple, mais seulement dans les sites à faible densité de reproducteurs. Une forte densité de reproducteurs pourrait limiter le choix de la femelle, possiblement en raison de l’agressivité des mâles ou du coût énergétique cumulatif de refuser des copulations hors couple. Globalement, j’ai non seulement montré que l’iridescence est un signal à composantes multiples pouvant jouer un rôle dans les deux constituantes du succès reproducteur, mais aussi que les conditions de compétition représentées par la densité de reproducteurs sont importantes à considérer pour avoir un portrait plus précis des patrons de sélection. Mon projet de recherche amène ainsi une meilleure compréhension de la sélection sexuelle en milieu naturel.

Page generated in 0.0681 seconds