Afficher la notice abrégée

dc.contributor.advisorRaspaud, André
dc.contributor.advisorWang, Weifan
dc.contributor.authorCHEN, Min
dc.contributor.otherZhu, Xuding
dc.date2010-11-17
dc.date.accessioned2020-12-14T21:17:01Z
dc.date.available2020-12-14T21:17:01Z
dc.identifier.urihttp://ori-oai.u-bordeaux1.fr/pdf/2010/CHEN_MIN_2010.pdf
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/22706
dc.identifier.nnt2010BOR14090
dc.description.abstractDans 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.
dc.description.abstractEnIn 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.
dc.language.isoen
dc.subjectGraphe planaire
dc.subjectColoration acyclique
dc.subjectColoration étoilée
dc.subjectSommets arboricité
dc.subjectHomomorphisme
dc.subjectDegré moyen maximum
dc.subjectGraphe de Petersen
dc.subjectCycle
dc.subject.enPlanar graph
dc.subject.enAcyclic coloring
dc.subject.enStar coloring
dc.subject.enVertex-arboricity
dc.subject.enHomomorphism
dc.subject.enMaximum average degree
dc.subject.enPetersen graph
dc.subject.enCycle
dc.titleColoration des sommets des graphes par la méthode de déchargement
dc.title.enVertex coloring of graphs via the discharging method
dc.typeThèses de doctorat
dc.contributor.jurypresidentSopena, Eric
bordeaux.hal.laboratoriesThèses de l'Université de Bordeaux avant 2014*
bordeaux.hal.laboratoriesLaboratoire bordelais de recherche en informatique
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.type.institutionBordeaux 1
bordeaux.thesis.disciplineInformatique
bordeaux.ecole.doctoraleÉcole doctorale de mathématiques et informatique (Talence, Gironde)
star.origin.linkhttps://www.theses.fr/2010BOR14090
dc.contributor.rapporteurChang, Gerard Jennhwa
dc.contributor.rapporteurHavet, Frédéric
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Coloration%20des%20sommets%20des%20graphes%20par%20la%20m%C3%A9thode%20de%20d%C3%A9chargement&rft.atitle=Coloration%20des%20sommets%20des%20graphes%20par%20la%20m%C3%A9thode%20de%20d%C3%A9chargement&rft.au=CHEN,%20Min&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée