Spelling suggestions: "subject:"5cyclic coloring"" "subject:"encyclic coloring""
1 |
Vertex coloring of graphs via the discharging method / Coloration des sommets des graphes par la méthode de déchargementChen, Min 17 November 2010 (has links)
Dans cette thèse, nous nous intéressons à differentes colorations des sommets d’un graphe et aux homomorphismes de graphes. Nous nous intéressons plus spécialement aux graphes planaires et aux graphes peu denses. Nous considérons la coloration propre des sommets, la coloration acyclique, la coloration étoilée, lak-forêt-coloration, la coloration fractionnaire et la version par liste de la plupart de ces concepts.Dans le Chapitre 2, nous cherchons des conditions suffisantes de 3-liste colorabilité des graphes planaires. Ces conditions sont exprimées en termes de sous-graphes interdits et nos résultats impliquent plusieurs résultats connus.La notion de la 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. Dans le Chapitre 3, on obtient des conditions suffisantes pour qu’un graphe planaire admette une k-coloration acyclique par liste avec k 2 f3; 4; 5g.Dans le Chapitre 4, nous montrons que tout graphe subcubique est 6-étoilé coloriable.D’autre part, Fertin, Raspaud et Reed ont montré que le graphe de Wagner ne peut pas être 5-étoilé-coloriable. Ce fait implique que notre résultat est optimal. De plus, nous obtenons des nouvelles bornes supérieures sur la choisissabilité étoilé d’un graphe planaire subcubique de maille donnée.Une k-forêt-coloration d’un graphe G est une application ¼ de l’ensemble des sommets V (G) de G dans l’ensemble de couleurs 1; 2; ¢ ¢ ¢ ; k telle que chaque classede couleur induit une forêt. Le sommet-arboricité de G est le plus petit entier ktel que G a k-forêt-coloration. Dans le Chapitre 5, nous prouvons une conjecture de Raspaud et Wang affirmant que tout graphe planaire sans triangles intersectants admet une sommet-arboricité au plus 2.Enfin, au Chapitre 6, nous nous concentrons sur le problème d’homomorphisme des graphes peu denses dans le graphe de Petersen. Plus précisément, nous prouvons que tout graphe sans triangles ayant un degré moyen maximum moins de 5=2 admet un homomorphisme dans le graphe de Petersen. En outre, nous montrons que la borne sur le degré moyen maximum est la meilleure possible. / In this thesis, we are interested in various vertex coloring and homomorphism problems of graphs with special emphasis on planar graphs and sparsegraphs. We consider proper vertex coloring, acyclic coloring, star coloring, forestcoloring, fractional coloring and the list version of most of these concepts.In Chapter 2, we consider the problem of finding sufficient conditions for a planargraph to be 3-choosable. These conditions are expressed in terms of forbiddensubgraphs and our results extend several known results.The notion of acyclic list coloring of planar graphs was introduced by Borodin,Fon-Der Flaass, Kostochka, Raspaud, and Sopena. They conjectured that everyplanar graph is acyclically 5-choosable. In Chapter 3, we obtain some sufficientconditions for planar graphs to be acyclically k-choosable with k 2 f3; 4; 5g.In Chapter 4, we prove that every subcubic graph is 6-star-colorable. On theother hand, Fertin, Raspaud and Reed showed that the Wagner graph cannot be5-star-colorable. This fact implies that our result is best possible. Moreover, weobtain new upper bounds on star choosability of planar subcubic graphs with givengirth.A k-forest-coloring of a graph G is a mapping ¼ from V (G) to the set f1; ¢ ¢ ¢ ; kgsuch that each color class induces a forest. The vertex-arboricity of G is the smallestinteger k such that G has a k-forest-coloring. In Chapter 5, we prove a conjecture ofRaspaud and Wang asserting that every planar graph without intersecting triangleshas vertex-arboricity at most 2.Finally, in Chapter 6, we focus on the homomorphism problems of sparse graphsto the Petersen graph. More precisely, we prove that every triangle-free graph withmaximum average degree less than 5=2 admits a homomorphism to the Petersengraph. Moreover, we show that the bound on the maximum average degree in ourresult is best possible.
|
2 |
Colorations de graphes sous contraintes / Graph coloring under constraintsHocquard, 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.
|
Page generated in 0.0772 seconds