Coloration circulaire et coloration acyclique par listes de graphes
Idioma
en
Thèses de doctorat
Fecha de defensa
2009-12-14Especialidad
Informatique
Escuela doctoral
École doctorale de mathématiques et informatique (Talence, Gironde)Resumen
Dans cette thèse, nous nous intéressons à la coloration circulaire des graphes planaires. Des bornes supérieures ont été données pour des graphes avec degré maximum borné, avec girth, la longueur de son plus petit cycle, ...Leer más >
Dans cette thèse, nous nous intéressons à la coloration circulaire des graphes planaires. Des bornes supérieures ont été données pour des graphes avec degré maximum borné, avec girth, la longueur de son plus petit cycle, bornée, avec des cycles manquants, etc. Ici nous donnerons de nouvelles bornes pour les graphes avec degré moyen maximum borné. Nous étudions également la coloration totale et la coloration (d,1)-totale de plusieurs familles infinies de graphes. Nous décrivons le nouveau concept de coloration (d,1)-totale circulaire. Enfin, nous discutons les conditions nécessaires pour qu'un graphe planaire admette une coloration acyclique par listes de taille 4.< Leer menos
Resumen en inglés
In this thesis, we study the circular coloring of planar graphs. Upper bounds have been given for graphs with bounded maximum degree, with bounded girth, that is the length of its smallest cycle, with missing cycles, and ...Leer más >
In this thesis, we study the circular coloring of planar graphs. Upper bounds have been given for graphs with bounded maximum degree, with bounded girth, that is the length of its smallest cycle, with missing cycles, and so on. It has also been studied for graphs with bounded maximum average degree. Here we give new upper bounds for that latter case. We also study the total coloring and (d,1)-total labeling of a few infinite families of graphs and describe the new concept of circular (d,1)-total labeling of graphs. In the last part, we will discuss conditions for a planar graph to be acyclically 4-choosable.< Leer menos
Palabras clave
Théorie des graphes
Coloration circulaire
Coloration acyclique par liste
Graphes planaires
Palabras clave en inglés
Graph theory
Circular coloring
Acyclic choosability
Planar graph
Orígen
Recolectado de STARCentros de investigación