Dissertations / Theses: 'Coloriage de graphe'

1

Legay, Sylvain. "Quelques problèmes d'algorithmique et combinatoires en théorie des grapphes." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLS030/document.

Full text

Abstract:

Le sujet de cette thèse est la théorie des graphes. Formellement, un graphe est un ensemble de sommets et un ensemble d’arêtes, c’est à dire de paires de sommets, qui relient les sommets. Cette thèse traite de différents problèmes de décisions binaires ou de minimisations liés à la notion de graphe, et cherche, pour chacun de ces problèmes, à déterminer sa classe de complexité, ou à fournir un algorithme. Le premier chapitre concerne le problème de trouver le plus petit sous-graphe connexe tropical dans un graphe sommet-colorié, c’est à dire le plus petit sous-graphe connexe contenant toutes les couleurs. Le deuxième chapitre concerne les problèmes d’homomorphisme tropical, une généralisation des problèmes de coloriage de graphe. On y trouve un lien entre ces problèmes et plusieurs classes de problèmes d’homomorphismes, dont la classe des Problèmes de Satisfaction de Contraintes. Le troisième chapitre concerne deux variantes lointaines du problème de domination, nommément les problèmes d’alliances globales dans un graphe pondéré et le problème de l’ensemble sûr. Le quatrième chapitre concerne la recherche d’une décomposition arborescente étoilée, c’est à dire une décomposition arborescente dont le rayon des sacs est 1. Enfin, le cinquième chapitre concerne une variante du problème de décider du comportement asymptotique de l’itéré du graphe des bicliques
This thesis is about graph theory. Formally, a graph is a set of vertices and a set of edges, which are pair of vertices, linking vertices. This thesis deals with various decision problem linked to the notion of graph, and, for each of these problem, try to find its complexity class, or to give an algorithm. The first chapter is about the problem of finding the smallest connected tropical subgraph of a vertex-colored graph, which is the smallest connecter subgraph containing every colors. The second chapter is about problems of tropical homomorphism, a generalization of coloring problem. A link between these problems and several other class of homomorphism problems can be found in this chapter, especially with the class of Constraint Satisfaction Problem. The third chapter is about two variant of the domination problem, namely the global alliance problems in a weighted graph and the safe set problem. The fourth chapter is about the problem of finding a star tree-decomposition, which is a tree-decomposition where the radius of bags is 1. Finally, the fifth chapter is about a variant of the problem of deciding the asymptotic behavior of the iterated biclique graph

APA, Harvard, Vancouver, ISO, and other styles

2

Xu, Renyu. "Quelques problèmes de coloration du graphe." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLS104/document.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

3

Pastor, Lucas. "Coloration, ensemble indépendant et structure de graphe." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAM071/document.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

4

Lecat, Clément. "Réduction de l'espace de recherche du Problème de la Somme Coloration Minimum d'un graphe." Thesis, Amiens, 2017. http://www.theses.fr/2017AMIE0033/document.

Full text

Abstract:

Le Problème de la Somme Coloration Minimum (MSCP) d'un graphe est un problème d'optimisation combinatoire dont l'objectif est de déterminer une coloration valide minimisant la somme des poids associés aux couleurs utilisées. Le nombre minimum de couleurs dans une solution optimale de MSCP est appelé la force du graphe, et la somme des poids des couleurs utilisées est appelée la somme chromatique du graphe. L'objectif de cette thèse a été d'étudier MSCP afin de proposer de nouvelles approches permettant sa résolution. La contribution de cette thèse est double. Premièrement, nous avons introduit deux nouvelles bornes supérieures de la force d'un graphe et une nouvelle borne inférieure de la somme chromatique, basées sur la notion de motif que nous avons adapté de la littérature. L'intérêt majeur de ces travaux est la réduction de l'espace des solutions de MSCP. Deuxièmement, nous avons proposé plusieurs approches de résolution exacte de MSCP. La première méthode consiste en une modélisation de MSCP en un formalisme MaxSAT partiel pondéré ou MinSAT partiel pondéré afin d'utiliser les solveurs MaxSAT/MinSAT de l'état de l'art pour résoudre MSCP. Nous avons montré que notre borne de la force du graphe permet de réduire grandement la taille des instances MaxSAT/MinSAT obtenues et de rendre les solveurs MaxSAT compétitifs pour résoudre MSCP. Les deux autres méthodes de résolution proposées sont des approches de type Branch-and-Bound appelées BBMSCP et 3LMSCP. La différence entre BBMSCP et 3LMSCP est que 3LMSCP exploite la partition du graphe en stables afin de ne pas considérer les colorations symétriques
The Minimum Sum Coloring Problem (MSCP) of a graph is an optimization problem whose the aim is to find a valid coloring such that the sum of weights associated to the used color is minimum. The minimum number of colors needed in an optimal solution is called the strength of the graph, and the sum of weights of the colors used in an optimal solution is called the chromatic sum of the graph. The aim of this thesis was to study the MSCP in order to propose new approaches for its resolution. The contribution of the thesis is twofold. First, we have introduced two upper bounds of the strength and one lower bound of the chromatic sum of a graph, based on a notion called motif adapted from the literature. These bounds allow to reduce significantly the search space of the MSCP. Second, we have proposed several exact resolution methods for the MSCP. The first method consists in modelling the MSCP to a weighted partial MaxSAT or a weighted partial MinSAT and solves the MSCP using state-of-the-art MaxSAT/MinSAT solvers. We have showed that our upper bound of the strength allows to improve substantially the MaxSAT/MinSAT encodings, and consequently, the MaxSAT solvers are competitive to solve the MSCP. The two other resolution methods are based on the Branch-and-Bound scheme and are called BBMSCP and 3LMSCP respectively. The difference between BBMSCP and 3LMSCP is that BBMSCP explores many symmetric colorings but 3LMSCP exploits the partitions of the graph into stables to avoid symmetric colorings

APA, Harvard, Vancouver, ISO, and other styles

5

Pierron, Théo. "Induction Schemes : From Language Separation to Graph Colorings." Thesis, Bordeaux, 2019. http://www.theses.fr/2019BORD0119/document.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

6

Gardi, Frédéric. "Ordonnancement avec exclusion mutuelle par un graphe d'intervalles ou d'une classe apparentée : complexité et algorithmes." Aix-Marseille 2, 2005. http://theses.univ-amu.fr.lama.univ-amu.fr/2005AIX22014.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Mortada, Maidoun. "The b-chromatic number of regular graphs." Thesis, Lyon 1, 2013. http://www.theses.fr/2013LYO10116.

Full text

Abstract:

Les deux problèmes majeurs considérés dans cette thèse : le b-coloration problème et le graphe emballage problème. 1. Le b-coloration problème : Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. EL Sahili et Kouider demandent s'il est vrai que chaque graphe d-régulier G avec le périmètre au moins 5 satisfait b(G) = d + 1. Blidia, Maffray et Zemir ont montré que la conjecture d'El Sahili et de Kouider est vraie pour d ≤ 6. En outre, la question a été résolue pour les graphes d-réguliers dans des conditions supplémentaires. Nous étudions la conjecture d'El Sahili et de Kouider en déterminant quand elle est possible et dans quelles conditions supplémentaires elle est vrai. Nous montrons que b(G) = d + 1 si G est un graphe d-régulier qui ne contient pas un cycle d'ordre 4 ni d'ordre 6. En outre, nous fournissons des conditions sur les sommets d'un graphe d-régulier G sans le cycle d'ordre 4 de sorte que b(G) = d + 1. Cabello et Jakovac ont prouvé si v(G) ≥ 2d3 - d2 + d, puis b(G) = d + 1, où G est un graphe d-régulier. Nous améliorons ce résultat en montrant que si v(G) ≥ 2d3 - 2d2 + 2d alors b(G) = d + 1 pour un graphe d-régulier G. 2. Emballage de graphe problème : Soit G un graphe d'ordre n. Considérer une permutation σ : V (G) → V (Kn), la fonction σ* : E(G) → E(Kn) telle que σ *(xy) = σ *(x) σ *(y) est la fonction induite par σ. Nous disons qu'il y a un emballage de k copies de G (dans le graphe complet Kn) s'il existe k permutations σi : V (G) → V (Kn), où i = 1, …, k, telles que σi*(E(G)) ∩ σj (E(G)) = ɸ pour i ≠ j. Un emballage de k copies d'un graphe G est appelé un k-placement de G. La puissance k d'un graphe G, noté par Gk, est un graphe avec le même ensemble de sommets que G et une arête entre deux sommets si et seulement si le distance entre ces deux sommets est au plus k. Kheddouci et al. ont prouvé que pour un arbre non-étoile T, il existe un 2-placement σ sur V (T). Nous introduisons pour la première fois le problème emballage marqué de graphe dans son graphe puissance
Two problems are considered in this thesis: the b-coloring problem and the graph packing problem. 1. The b-Coloring Problem : A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least a vertex in each other color class. The b-chromatic number of a graph G, denoted by b(G), is the maximum number t such that G admits a b-coloring with t colors. El Sahili and Kouider asked whether it is true that every d-regular graph G with girth at least 5 satisfies b(G) = d + 1. Blidia, Maffray and Zemir proved that the conjecture is true for d ≤ 6. Also, the question was solved for d-regular graphs with supplementary conditions. We study El Sahili and Kouider conjecture by determining when it is possible and under what supplementary conditions it is true. We prove that b(G) = d+1 if G is a d-regular graph containing neither a cycle of order 4 nor of order 6. Then, we provide specific conditions on the vertices of a d-regular graph G with no cycle of order 4 so that b(G) = d + 1. Cabello and Jakovac proved that if v(G) ≥ 2d3 - d2 + d, then b(G) = d + 1, where G is a d-regular graph. We improve this bound by proving that if v(G) ≥ 2d3 - 2d2 + 2d, then b(G) = d+1 for a d-regular graph G. 2. Graph Packing Problem : Graph packing problem is a classical problem in graph theory and has been extensively studied since the early 70's. Consider a permutation σ : V (G) → V (Kn), the function σ* : E(G) → E(Kn) such that σ *(xy) = σ *(x) σ *(y) is the function induced by σ. We say that there is a packing of k copies of G into the complete graph Kn if there exist k permutations σ i : V (G) → V (Kn), where i = 1,…, k, such that σ*i (E(G)) ∩ σ*j (E(G)) = ɸ for I ≠ j. A packing of k copies of a graph G will be called a k-placement of G. The kth power Gk of a graph G is the supergraph of G formed by adding an edge between all pairs of vertices of G with distance at most k. Kheddouci et al. proved that for any non-star tree T there exists a 2-placement σ on V (T). We introduce a new variant of graph packing problem, called the labeled packing of a graph into its power graph

APA, Harvard, Vancouver, ISO, and other styles

8

Chen, Min. "Vertex coloring of graphs via the discharging method." Thesis, Bordeaux 1, 2010. http://www.theses.fr/2010BOR14090/document.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

9

Weinberg, Benjamin Talbi El-Ghazali. "Analyse et résolution approchée de problèmes d'optimisation combinatoire application au problème de coloration de graphe /." Villeneuve d'Ascq : Université des sciences et technologies de Lille, 2007. https://iris.univ-lille1.fr/dspace/handle/1908/973.

Full text

Abstract:

Reproduction de : Thèse de doctorat : Informatique : Lille 1 : 2004.
N° d'ordre (Lille 1) : 3467. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. 9 p.

APA, Harvard, Vancouver, ISO, and other styles

10

Weinberg, Benjamin. "Analyse et résolution approchée de problèmes d'optimisation combinatoire : application au problème de coloration de graphe." Lille 1, 2004. https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/2004/50376-2004-Weinberg.pdf.

Full text

Abstract:

Nous avons exploré plusieurs aspects théoriques et expérimentaux de l'optimisation combinatoire. Premièrement, nous avons défini une notion de structure permettant de s'échapper du résultat du théorème du No Free Lunch. Deuxièmement nous avons formalisé la symétrie de l'espace de recherche des problèmes de partitionnements. A l'aide de cette formalisation, nous pûmes concevoir des outils travaillant efficacement sur cette espace. Plus précisément nous avons développé un test d'égalité, une mesure de distance et un nouvel opérateur de Cross over. Nous avons utilisé ces résultats pour classifier les benchmarks classique de la coloration de graphe. Pour finir, nous avons développe pour ce problème une métaheuristique parallèle qui équilibre l'intensification et la diversification pendant la recherche.

APA, Harvard, Vancouver, ISO, and other styles

11

Lagoutte, Aurélie. "Interactions entre les Cliques et les Stables dans un Graphe." Thesis, Lyon, École normale supérieure, 2015. http://www.theses.fr/2015ENSL1012/document.

Full text

Abstract:

Cette thèse s'intéresse à différents types d'interactions entre les cliques et les stables, deux objets très importants en théorie des graphes, ainsi qu'aux relations entre ces différentes interactions. En premier lieu, nous nous intéressons au problème classique de coloration de graphes, qui peut s'exprimer comme une partition des sommets du graphe en stables. Nous présentons un résultat de coloration pour les graphes sans triangles ni cycles pairs de longueur au moins 6. Dans un deuxième temps, nous prouvons la propriété d'Erdös-Hajnal, qui affirme que la taille maximale d'une clique ou d'un stable devient polynomiale (contre logarithmique dans les graphes aléatoires) dans le cas des graphes sans chemin induit à k sommets ni son complémentaire, quel que soit k.Enfin, un problème moins connu est la Clique-Stable séparation, où l'on cherche un ensemble de coupes permettant de séparer toute clique de tout stable. Cette notion a été introduite par Yannakakis lors de l’étude des formulations étendues du polytope des stables dans un graphe parfait. Il prouve qu’il existe toujours un séparateur Clique-Stable de taille quasi-polynomiale, et se demande si l'on peut se limiter à une taille polynomiale. Göös a récemment fourni une réponse négative, mais la question se pose encore pour des classes de graphes restreintes, en particulier pour les graphes parfaits. Nous prouvons une borne polynomiale pour la Clique-Stable séparation dans les graphes aléatoires et dans plusieurs classes héréditaires, en utilisant notamment des outils communs à l'étude de la conjecture d'Erdös-Hajnal. Nous décrivons également une équivalence entre la Clique-Stable séparation et deux autres problèmes : la conjecture d'Alon-Saks-Seymour généralisée et le Problème Têtu, un problème de Satisfaction de Contraintes
This thesis is concerned with different types of interactions between cliques and stable sets, two very important objects in graph theory, as well as with the connections between these interactions. At first, we study the classical problem of graph coloring, which can be stated in terms of partioning the vertices of the graph into stable sets. We present a coloring result for graphs with no triangle and no induced cycle of even length at least six. Secondly, we study the Erdös-Hajnal property, which asserts that the maximum size of a clique or a stable set is polynomial (instead of logarithmic in random graphs). We prove that the property holds for graphs with no induced path on k vertices and its complement.Then, we study the Clique-Stable Set Separation, which is a less known problem. The question is about the order of magnitude of the number of cuts needed to separate all the cliques from all the stable sets. This notion was introduced by Yannakakis when he studied extended formulations of the stable set polytope in perfect graphs. He proved that a quasi-polynomial number of cuts is always enough, and he asked if a polynomial number of cuts could suffice. Göös has just given a negative answer, but the question is open for restricted classes of graphs, in particular for perfect graphs. We prove that a polynomial number of cuts is enough for random graphs, and in several hereditary classes. To this end, some tools developed in the study of the Erdös-Hajnal property appear to be very helpful. We also establish the equivalence between the Clique-Stable set Separation problem and two other statements: the generalized Alon-Saks-Seymour conjecture and the Stubborn Problem, a Constraint Satisfaction Problem

APA, Harvard, Vancouver, ISO, and other styles

12

Gastineau, Nicolas. "Partitionnement, recouvrement et colorabilité dans les graphes." Thesis, Dijon, 2014. http://www.theses.fr/2014DIJOS014/document.

Full text

Abstract:

Nos recherches traitent de coloration de graphes avec des contraintes de distance (coloration de packing) ou des contraintes sur le voisinage (coloration de Grundy). Soit S={si| i in N*} une série croissante d’entiers. Une S -coloration de packing est une coloration propre de sommets telle que tout ensemble coloré i est un si-packing (un ensemble où tous les sommets sont à distance mutuelle supérieure à si). Un graphe G est (s1,... ,sk)-colorable si il existe une S -coloration de packing de G avec les couleurs 1, ...,,k. Une coloration de Grundy est une coloration propre de sommets telle que pour tout sommet u coloré i, u est adjacent à un sommet coloré j, pour chaque ji. Ces résultats nous permettent de déterminer des S-colorations de packings de ces grilles pour plusieurs séries d’entiers. Nous examinons une classe de graphe jamais étudiée en ce qui concerne la S -coloration de packing: les graphes subcubiques. Nous déterminons que tous les graphes subcubiques sont (1,2,2,2,2,2,2)-colorables et (1,1,2,2,3)-colorables. Un certain nombre de résultats sont prouvés pour certaines sous-classes des graphes subcubiques. Pour finir, nous nous intéressons au nombre de Grundy des graphes réguliers. Nous déterminons une caractérisation des graphes cubiques avec un nombre de Grundy de 4. De plus, nous prouvons que tous les graphes r-réguliers sans carré induit ont pour nombre de Grundy de r+1, pour r<5
Our research are about graph coloring with distance constraints (packing coloring) or neighborhood constraints (Grundy coloring). Let S={si| i in N*} be a non decreasing sequence of integers. An S-packing coloring is a proper coloring such that every set of color i is an si-packing (a set of vertices at pairwise distance greater than si). A graph G is (s1,... ,sk)-colorable if there exists a packing coloring of G with colors 1,... ,k. A Grundy coloring is a proper vertex coloring such that for every vertex of color i, u is adjacent to a vertex of color j, for each ji. These results allow us to determine S-packing coloring of these lattices for several sequences of integers. We examine a class of graph that has never been studied for S-packing coloring: the subcubic graphs. We determine that every subcubic graph is (1,2,2,2,2,2,2)-colorable and (1,1,2,2,3)-colorable. Few results are proven about some subclasses. Finally, we study the Grundy number of regular graphs. We determine a characterization of the cubic graphs with Grundy number 4. Moreover, we prove that every r-regular graph without induced square has Grundy number r+1, for r<5

APA, Harvard, Vancouver, ISO, and other styles

13

Le, Ngoc Khang. "Detecting and Coloring some Graph Classes." Thesis, Lyon, 2018. http://www.theses.fr/2018LYSEN021/document.

Full text

Abstract:

Les graphes sont des structures mathématiques utilisées pour modéliser les relations par paires entre objets. Malgré leur structure simple, les graphes ont des applications dans divers domaines tels que l'informatique, la physique, la biologie et la sociologie. L'objectif principal de ce travail est de continuer l'étude des problèmes de coloration et de détection dans le cadre de classes de graphes fermées par sous-graphes induits (que nous appelons classes de graphes héréditaires).La première classe que nous considérons est graphes sans ISK4 - les graphes qui ne contiennent aucune subdivision de en tant que sous-graphe induit. Nous montrons que le nombre chromatique de cette classe est limité à 24, une amélioration considérable par rapport à la borne existant précédemment. Nous donnons également une bien meilleure limite dans le cas sans triangle. De plus, nous prouvons qu'il existe un algorithme de complexité pour détecter cette classe, ce qui répond à une question de Chudnovsky et al. et Lévêque et al.La deuxième classe que nous étudions est celle des graphes sans trou pair et sans étoile d’articulation. Cela est motivé par l'utilisation de la technique de décomposition pour résoudre certains problèmes d'optimisation. Nous garantissons la fonction χ-bounding optimale pour cette classe. Nous montrons que la classe a rank-width bornée, ce qui implique l'existence d'un algorithme de coloration en temps polynomial. Enfin, la coloration gloutonne connexe dans les graphes sans griffes est considérée. Une façon naturelle de colorier un graphe est d'avoir un ordre de ses sommets et d'affecter pour chaque sommet la première couleur disponible. Beaucoup de recherches ont été faites pour des ordres généraux. Cependant, nous connaissons très peu de choses sur la caractérisation des bons graphes par rapport aux ordres connexes. Un graphe est bon si pour chaque sous-graphe induit connexe de , chaque ordre connexe donne à une coloration optimale. Nous donnons la caractérisation complète de bons graphes sans griffes en termes de sous-graphes induits minimaux interdits
Graphs are mathematical structures used to model pairwise relations between objects. Despite their simple structures, graphs have applications in various areas like computer science, physics, biology and sociology. The main focus of this work is to continue the study of the coloring and detecting problems in the setting of graph classes closed under taking induced subgraphs (which we call hereditary graph classes). The first class we consider is ISK4-free graphs - the graphs that do not contain any subdivision of K4 as an induced subgraph. We prove that the chromatic number of this class is bounded by 24, a huge improvement compared to the best-known bound. We also give a much better bound in the triangle-free case. Furthermore, we prove that there exists an O(n 9) algorithm for detecting this class, which answers a question by Chudnovsky et al. and Lévêque et al. The second class we study is even-hole-free graphs with no star cutset. This was motivated by the use of decomposition technique in solving some optimization problems. We prove the optimal χ -bounding function for this class and show that it has bounded rank-width, which implies the existence of a polynomial-time coloring algorithm.Finally, the connected greedy coloring in claw-free graphs is considered. A natural way to color a graph is to have an order of its vertices and assign for each vertex the first available color. A lot of researches have been done for general orders. However, we know very little about the characterization of good graphs with respect to connected orders. A graph G is good if for every connected induced subgraph H of G, every connected order gives H an optimal coloring. We give the complete characterization of good claw-free graphs in terms of minimal forbidden induced subgraphs

APA, Harvard, Vancouver, ISO, and other styles

14

Ternier, Ian-Christopher. "Résolution exacte du Problème de Coloration de Graphe et ses variantes." Thesis, Paris Sciences et Lettres (ComUE), 2017. http://www.theses.fr/2017PSLED060/document.

Full text

Abstract:

Dans un graphe non orienté, le Problème de Coloration de Graphe (PCG) consiste à assigner à chaque sommet du graphe une couleur de telle sorte qu'aucune paire de sommets adjacents n'aient la même couleur et le nombre total de couleurs est minimisé. DSATUR est un algorithme exact efficace pour résoudre le PCG. Un de ses défauts est qu'une borne inférieure est calculée une seule fois au noeud racine de l'algorithme de branchement, et n'est jamais mise à jour. Notre nouvelle version de DSATUR surpasse l'état de l'art pour un ensemble d'instances aléatoires à haute densité, augmentant significativement la taille des instances résolues. Nous étudions trois formulations PLNE pour le Problème de la Somme Chromatique Minimale (PSCM). Chaque couleur est représentée par un entier naturel. Le PSCM cherche à minimiser la somme des cardinalités des sous-ensembles des sommets recevant la même couleur, pondérés par l'entier correspondant à la couleur, de telle sorte que toute paire de sommets adjacents reçoive des couleurs différentes. Nous nous concentrons sur l'étude d'une formulation étendue et proposons un algorithme de Branch-and-Price
Given an undirected graph, the Vertex Coloring Problem (VCP) consists of assigning a color to each vertex of the graph such that two adjacent vertices do not share the same color and the total number of colors is minimized. DSATUR is an effective exact algorithm for the VCP. We introduce new lower bounding techniques enabling the computing of a lower bound at each node of the branching scheme. Our new DSATUR outperforms the state of the art for random VCP instances with high density, significantly increasing the size of solvable instances. Similar results can be achieved for a subset of high density DIMACS instances. We study three ILP formulations for the Minimum Sum Coloring Problem (MSCP). The problem is an extension of the classical Vertex Coloring Problem in which each color is represented by a positive natural number. The MSCP asks to minimize the sum of the cardinality of subsets of vertices receiving the same color, weighted by the index of the color, while ensuring that vertices linked by an edge receive different colors. We focus on studying an extended formulation and devise a complete Branch-and-Price algorithm

APA, Harvard, Vancouver, ISO, and other styles

15

Sun, Pak Kiu. "Incidence coloring : origins, developments and relation with other colorings." HKBU Institutional Repository, 2007. http://repository.hkbu.edu.hk/etd_ra/826.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Charpentier, Clément. "Coloration, jeux et marquages dans les graphes." Thesis, Bordeaux, 2014. http://www.theses.fr/2014BORD0023/document.

Full text

Abstract:

Nous étudions plusieurs problèmes de coloration dans les graphes, pour certains avec une composante ludique. La coloration à distance 2 d'un graphe est une coloration de ses sommets telle que deux sommets à distance au plus 2 ont des couleurs différentes. Le L(p; q)-étiquetage est une généralisation de ce problème ou les contraintes à distance 1 et 2 sont différentes. Nous donnons des résultats pour ces deux problèmes dans plusieurs classes de graphes peu denses (ayant un faible degré moyen maximum).Le jeu de coloration sur un graphe est un jeu ou deux joueurs, Alice et Bob, colorent tour à tour un des sommets non coloriés d'un graphe, construisant ainsi une coloration propre partielle de plus en plus étendue de ce graphe. Alice tente d'étendre la coloration à l'ensemble du graphe, et Bob tente de l'en empêcher. Nous travaillons sur un invariant de graphe, le degré minmax, dont l'étude permet de déduire des résultats pour le jeu de coloration via l'étude d'un problème structurel, la (1; k)-décomposition d'un graphe, c'est-à-dire la partition de ses arêtes en une forêt et un sous-graphe de degré inférieur ou égal à k.Nous travaillons enfin sur une variante du jeu de coloration nommée jeu de coloration d'incidences, ou Alice et Bob colorient les incidences d'un graphe, pour lequel nous donnons une stratégie efficace pour Alice.Enfin, tout au long de notre mémoire, nous étudions les liens entre la notion de coloration est celle de marquage. Un marquage est un ordre sur les sommets (ou arêtes, ou incidences...) d'un graphe possédant des caractéristiques utiles pour le colorer. Pour nos différents problèmes, nous questionnons l'utilité ou les limites de l'usage de cette notion
We study several problems of graph coloring, some of them with a game component.A 2-distance coloring of a graph is a vertex coloring where two vertices at distanceat most two have different colors. A L(p; q)-labeling is a generalisation of the distance-2coloring where constraints are different at distance 1 and 2. We give results for thesetwo problems in several classes of sparse graphs (with a low maximal average degree).The coloring game on a graph is a game where two players, Alice and Bob, taketurns coloring an uncolored vertex of the graph, constructing together a proper partialcoloring of the graph extending as time moves on. Alice try to extend the coloringto the whole graph, and Bob try to prevent her to win. We study a graph invariant,the minmax degree, who has consequences on the coloring game through the notion of(1; k)-decomposition of a graph, which is the partition of its edge set into a forest and asubgraph of degree bounded by k.We finally study a variant of the coloring game named incidence coloring game, whereAlice and Bob are coloring the incidences of a graph, and for which we give an efficientstrategy for Alice.Finally, during our thesis, we study the connections between coloring and marking,which is an order on the vertices of a graph (or its edges, or its incidences) havingproperties usefull for its coloring. For our problems, we try to determine the utility andthe limits of a marking-based approach of coloring problems

APA, Harvard, Vancouver, ISO, and other styles

17

Duffy, Christopher. "Homomorphisms of (j, k)-mixed graphs." Thesis, Bordeaux, 2015. http://hdl.handle.net/1828/6601.

Full text

Abstract:

A mixed graph is a simple graph in which a subset of the edges have been assigned directions to form arcs. For non-negative integers j and k, a (j, k)−mixed graph is a mixed graph with j types of arcs and k types of edges. The collection of (j, k)−mixed graphs contains simple graphs ((0,1)−mixed graphs), oriented graphs ((1,0)-mixed graphs) and k−edge-coloured graphs ((0, k)−mixed graphs). A homomorphism is a vertex mapping from one (j,k)−mixed graph to another in which edge type is preserved, and arc type and direction are preserved. An m−colouring of a (j, k)−mixed graph is a homomorphism from that graph to a target with m vertices. The (j, k)−chromatic number of a (j, k)−mixed graph is the least m such that an m−colouring exists. When (j, k) = (0, 1), we see that these definitions are consistent with the usual definitions of graph homomorphism and graph colouring. Similarly, when (j, k) = (1, 0) and (j, k) = (0, k) these definitions are consistent with the usual definitions of homomorphism and colouring for oriented graphs and k−edge-coloured graphs, respectively. In this thesis we study the (j, k)−chromatic number and related parameters for different families of graphs, focussing particularly on the (1, 0)−chromatic number, more commonly called the oriented chromatic number, and the (0, k)−chromatic number. In examining oriented graphs, we provide improvements to the upper and lower bounds for the oriented chromatic number of the families of oriented graphs with maximum degree 3 and 4. We generalise the work of Sherk and MacGillivray on the 2−dipath chromatic number, to consider colourings in which vertices at the ends of iii a directed path of length at most k must receive different colours. We examine the implications of the work of Smolikova on simple colourings to study of the oriented chromatic number of the family of oriented planar graphs. In examining k−edge-coloured graphs we provide improvements to the upper and lower bounds for the family of 2−edge-coloured graphs with maximum degree 3. In doing so, we define the alternating 2−path chromatic number of k−edge-coloured graphs, a parameter similar in spirit to the 2−dipath chromatic number for oriented graphs. We also consider a notion of simple colouring for k−edge-coloured graphs, and show that the methods employed by Smolikova ́ for simple colourings of oriented graphs may be adapted to k−edge-coloured graphs. In addition to considering vertex colourings, we also consider incidence colourings of both graphs and digraphs. Using systems of distinct representatives, we provide a new characterisation of the incidence chromatic number. We define the oriented incidence chromatic number and find, by way of digraph homomorphism, a connection between the oriented incidence chromatic number and the chromatic number of the underlying graph. This connection motivates our study of the oriented incidence chromatic number of symmetric complete digraphs.
Graduate

APA, Harvard, Vancouver, ISO, and other styles

18

Sen, Sagnik. "A contribution to the theory of graph homomorphisms and colorings." Phd thesis, Bordeaux, 2014. http://tel.archives-ouvertes.fr/tel-00960893.

Full text

Abstract:

Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes.

APA, Harvard, Vancouver, ISO, and other styles

19

Tahraoui, Mohammed Amin. "Coloring, packing and embedding of graphs." Phd thesis, Université Claude Bernard - Lyon I, 2012. http://tel.archives-ouvertes.fr/tel-00995041.

Full text

Abstract:

In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.

APA, Harvard, Vancouver, ISO, and other styles

20

Macon, Lisa. "ALMOST REGULAR GRAPHS AND EDGE FACE COLORINGS OF PLANE GRAPHS." Doctoral diss., University of Central Florida, 2009. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/2480.

Full text

Abstract:

Regular graphs are graphs in which all vertices have the same degree. Many properties of these graphs are known. Such graphs play an important role in modeling network configurations where equipment limitations impose a restriction on the maximum number of links emanating from a node. These limitations do not enforce strict regularity, and it becomes interesting to investigate nonregular graphs that are in some sense close to regular. This dissertation explores a particular class of almost regular graphs in detail and defines generalizations on this class. A linear-time algorithm for the creation of arbitrarily large graphs of the discussed class is provided, and a polynomial-time algorithm for recognizing graphs in the class is given. Several invariants for the class are discussed. The edge-face chromatic number χef of a plane graph G is the minimum number of colors that must be assigned to the edges and faces of G such that no edge or face of G receives the same color as an edge or face with which it is incident or adjacent. A well-known result for the upper bound of χef exists for graphs with maximum degree Δ ≥ 10. We present a tight upper bound for plane graphs with Δ = 9.
Ph.D.
Department of Mathematics
Sciences
Mathematics PhD

APA, Harvard, Vancouver, ISO, and other styles

21

Yerger, Carl Roger Jr. "Color-critical graphs on surfaces." Diss., Georgia Institute of Technology, 2010. http://hdl.handle.net/1853/37197.

Full text

Abstract:

A graph is (t+1)-critical if it is not t-colorable, but every proper subgraph is. In this thesis, we study the structure of critical graphs on higher surfaces. One major result in this area is Carsten Thomassen's proof that there are finitely many 6-critical graphs on a fixed surface. This proof involves a structural theorem about a precolored cycle C of length q. In general terms, he proves that a coloring, c, of C, can be extended inside the cycle, or there exists a subgraph H with at most a number of vertices exponential in q such that c can not be extended to a 5-coloring of H. In Chapter 2, we proved an alternative proof that reduces the number of vertices in H to be cubic in q. In Chapter 3, we find the nine 6-critical graphs among all graphs embeddable on the Klein bottle. In Chapter 4, we prove a result concerning critical graphs related to an analogue of Steinberg's conjecture for higher surfaces. We show that if G is a 4-critical graph embedded on surface S, with Euler genus g and has no cycles of length four through ten, then G has at most 2442g + 37 vertices.

APA, Harvard, Vancouver, ISO, and other styles

22

Roussel, Nicolas. "Circular coloring and acyclic choosability of graphs." Thesis, Bordeaux 1, 2009. http://www.theses.fr/2009BOR13889/document.

Full text

Abstract:

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
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

APA, Harvard, Vancouver, ISO, and other styles

23

Heinrich, Marc. "Reconfiguration and combinatorial games." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSE1102/document.

Full text

Abstract:

Cette thèse explore des problématiques liées aux jeux. Les jeux qui nous intéressent sont ceux pour lesquels il n'y a pas d'information cachée: tout les joueurs ont accès à toute l'information relative au jeu; il n'y a pas non plus d'aléa. Certains jeux de société (comme les échecs ou le go) satisfont ces propriétés et sont représentatifs des jeux que nous considérons ici. La notion de stratégie est au centre de l'étude de ces jeux. En termes simples, une stratégie est une façon de jouer qui permet de s'assurer un certain résultat. La question centrale, à la fois quand on joue à un jeu et quand on l'étudie, est le problème de trouver la 'meilleure' stratégie, qui assure la victoire du joueur qui l'applique. Dans cette thèse, nous considérons à la fois des jeux à un joueurs, appelés puzzles combinatoires, et des jeux à deux joueurs. Le Rubik's cube, Rush-Hour, et le taquin sont des exemples biens connus de puzzles combinatoires. Récemment, un certain nombre de jeux -- des jeux à un joueur notamment -- ont connu un regain d'intérêt en tant qu'objets d'étude dans un domaine plus grand appelé reconfiguration. Les puzzles que l'on vient de mentionner peuvent tous être décrit de la façon suivante: il y a un ensemble de configurations, qui représente tous les états possibles du jeu; et le joueur est autorisé à transformer une configuration en une autre à via un certain nombre de règles. Le but est d'atteindre une certaine configuration cible à partir d'une configuration initiale. Le domaine de la reconfiguration étend cette définition à des problèmes de recherche: l'ensemble des configurations devient l'ensemble des solutions à une instance d'un problème donné, et l'on se demande si l'on peut transformer une solution donnée en une autre en utilisant uniquement un ensemble de règles de transformation précises. La recherche sur ce type de problèmes a été guidée par des motivations algorithmiques: ce processus peut être vu comme un moyen d'adapter une solution déjà en place en une nouvelle solution à l'aide de petits changements locaux; et des connections avec d'autres problèmes comme la génération aléatoire, ainsi que des problèmes de physique statistique. Les jeux à deux joueurs, qui sont aussi appelés jeux combinatoires, ont été étudiés depuis le début du XXème siècle avec les travaux de Bouton, continués par Berlekamp, Conway et Guy avec le développement d'une théorie unifiant un certain nombre de jeux classiques. Ce travail se focalise sur des joueurs parfaits, c'est à dire qui choisissent toujours le coup optimal. Notre but est de caractériser lequel des deux joueurs possède une stratégie qui lui assure la victoire, quelque soient les coups de son adversaire. Cette approche est au coeur de ce qui est appelé la Théorie des Jeux Combinatoires. Une grande parties des recherche est focalisée sur des 'jeux mathématiques', qui sont des jeux inventés par des mathématiciens, souvent avec des règles très simples, et rarement connus en dehors de la recherche. La motivation principale pour étudier ces jeux est la présence de liens parfois surprenant entre ces jeux et d'autres domaines des mathématiques comme entre autre la théorie des nombres, les automates ou les systèmes dynamiques. Dans cette thèse, nous étudions ainsi des jeux à un et deux joueurs. Nous nous intéressons tout particulièrement à la complexité de ces jeux, c'est à dire évaluer à quel point il est difficile (d'un point de vue algorithmique) de calculer une stratégie gagnante. Nous nous intéressons aussi à leur structure et à certaines propriétés qu'ils peuve satisfaire. Finalement, un des outils principaux dans cette étude est la notion de graphe, et nous utilisons notamment des méthodes et des techniques provenant de théorie des graphes pour résoudre ces problèmes
This thesis explores problems related to games. The games that we consider in this study are games for which there is no hidden information: all the players have access to all the information related to the game; there is also no randomness and everything is deterministic. A few well-known board games (such as chess or go) fall in this category and are representative of the kinds of games that we consider here. Central to the study of these games is the notion of strategy, which roughly speaking, is a way of playing which ensures a certain objective. The main question of interest, when both playing and studying a game, is the problem of finding the 'best' strategy, which secures the victory for the player following it. In this thesis, we consider both one-player games, also called combinatorial puzzles, and two-player games. Examples of combinatorial puzzles include Rubik's cube, Rush-Hour, Sokoban, the 15 puzzle, or peg solitaire. Recently, some types of one-player games in particular have received a strong regain of interest as part of the larger area of reconfiguration problems. The puzzles we described above can all be described in the following way: there is a set of configurations, which represents all the possible states of the game; and the player is allowed to transform a configuration using a prescribed set of moves. Starting from an initial configuration, the goal is to reach a target configuration by a succession of valid moves. Reconfiguration extends this definition to any search problem: the set of configuration becomes the set of solutions to an instance of a given problem, and we ask whether we can transform one given solution to another using only a prescribed set of moves. Hence, in addition to the combinatorial puzzles, reconfiguration problems also include many `games' which are not played by humans anymore but are instead mathematical problems sharing a lot of similarities with combinatorial puzzles. The study of reconfiguration problems has been driven by many different motivations. It has algorithmic applications: it can be seen as a way to adapt a current solution already in place to reach a new one by only making small local changes. It is also connected to other problems such as random sampling, approximate counting or problems coming from statistical physics. It can also be used as a tool for understanding the performance of some heuristic algorithms based on local modifications of solutions such as local search. Two-player games, which are also called combinatorial games, have been studied since the beginning of the twentieth century, with the works of Bouton which were continued with the development of a nice theory by Berlekamp, Conway, and Guy, unifying a certain number of classical games. We focus in this study on perfect strategies (i.e., players always choosing the best possible move), and try to characterize who wins under perfect play for various games. This approach is at the heart of what is called Combinatorial Game Theory. Most of the research in this area is focused on `math games' which are games invented by mathematicians, often with simple rules and almost never played by humans. The main motivation for studying these games comes from the nice, and sometimes unexpected connections these games have with other areas of mathematics, such as for example number theory, automatons, or dynamical systems. In this thesis, we study one- and two-player games. The questions we consider are often related to complexity. Complexity theory consists in trying to classify problems depending on their hardness. By hardness we mean to quantify how much time it would take for a computer to solve the problem. An other aspect of this research consists in investigating structural properties that these games can satisfy. Finally, one of our main tools is the notion of graph, and we use in particular methods and techniques from graph theory to answer the different questions we just mentioned

APA, Harvard, Vancouver, ISO, and other styles

24

Gajewar, Amita Surendra. "Approximate edge 3-coloring of cubic graphs." Thesis, Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/29735.

Full text

Abstract:

Thesis (M. S.)--Computing, Georgia Institute of Technology, 2009.
Committee Chair: Prof. Richard Lipton; Committee Member: Prof. Dana Randall; Committee Member: Prof. H. Venkateswaran. Part of the SMARTech Electronic Thesis and Dissertation Collection.

APA, Harvard, Vancouver, ISO, and other styles

25

Bonamy, Marthe. "Global discharging methods for coloring problems in graphs." Thesis, Montpellier, 2015. http://www.theses.fr/2015MONTS261.

Full text

Abstract:

Cette thèse s'inscrit dans le cadre de la théorie des graphes, et porte plus particulièrement sur des problèmes de coloration de graphes. Dans cette thèse, nous nous intéressons à l'utilisation et au développement de la méthode de déchargement, un argument de comptage qui exploite fortement la structure du graphe. Cette méthode est décisive dans la preuve du Théorème des Quatre Couleurs. Nous donnons d'abord une vue d'ensemble des outils de déchargement que nous utilisons dans ce travail, entre les méthodes élégantes mises en application, et les astuces développées. Dans le cadre de la coloration d'arêtes par liste, nous résolvons la Conjecture de Coloration par Liste faible dans le cas des graphes planaires de degré maximum 8, en prouvant qu'on peut colorier par liste les arêtes de ces derniers avec 9 couleurs seulement. Ceci améliore un résultat de Borodin de 1990. Enfin, nous présentons nos résultats dans le cadre de la coloration de carrés, où il s'agit de colorier les sommets sans qu'il y ait deux sommets adjacents ou avec un voisin commun qui soient de la même couleur. On s'intéresse en particulier à des conditions suffisantes sur la densité du graphe (c-à-d le degré moyen maximum d'un sous-graphe) pour qu'on puisse colorier son carré avec peu de couleurs
This thesis falls within graph theory, and deals more precisely with graph coloring problems. In this thesis, we use and develop the discharging method, a counting argument that makes strong advantage of the graph structure. This method is decisive in the proof of the Four Color Theorem. We first give an illustrated overview of the discharging tools that are used for this work: nice methods that we apply, and handy tricks that we develop. In the realm of list edge coloring, we most notably prove that the weak List Coloring Conjecture is true for planar graphs of maximum degree 8 (i.e. that they are edge 9-choosable), thus improving over a result of Borodin from 1990. We finally present our results about square coloring, where the goal is to color the vertices in such a way that two vertices that are adjacent or have a common neighbor receive different colors. We look in particular into sufficient conditions on the density of a graph (i.e. the maximum average degree of a subgraph) for its square to be colorable with few colo

APA, Harvard, Vancouver, ISO, and other styles

26

Normann, Per. "Parallel graph coloring : Parallel graph coloring on multi-core CPUs." Thesis, Uppsala universitet, Avdelningen för beräkningsvetenskap, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-227656.

Full text

Abstract:

In recent times an evident trend in hardware is to opt for multi-core CPUs. This has lead to a situation where an increasing number of sequential algorithms are parallelized to fit these new multi-core environments. The greedy Multi-Coloring algorithm is a strictly sequential algorithm that is used in a wide range of applications. The application in focus is on decomposition by graph coloring for preconditioning techniques suitable for iterative solvers like the and methods. In order to perform all phases of these iterative solvers in parallel the graph analysis phase needs to be parallelized. Albeit many attempts have been made to parallelize graph coloring non of these attempts have successfully put the greedy Multi-Coloring algorithm into obsolescence. In this work techniques for parallel graph coloring are proposed and studied. Quantitative results, which represent the number of colors, confirm that the best new algorithm, the Normann algorithm, is performing on the same level as the greedy Multi-Coloring algorithm. Furthermore, in multi-core environments the parallel Normann algorithm fully outperforms the classical greedy Multi-Coloring algorithm for all large test matrices. With the features of the Normann algorithm quantified and presented in this work it is now possible to perform all phases of iterative solvers like and methods in parallel.

APA, Harvard, Vancouver, ISO, and other styles

27

Araujo, Julio. "Graph coloring and graph convexity." Nice, 2012. http://www.theses.fr/2012NICE4032.

Full text

Abstract:

Dans cette thèse, nous étudions plusieurs problèmes de théorie des graphes concernant la coloration et la convexité des graphes. La plupart des résultats figurant ici sont liés à la complexité de calcul de ces problèmes pour certaines classes de graphes. Dans la première, et principale, partie de cette thèse, nous traitons la coloration des graphes qui est l’un des domaines les plus étudiés de théorie des graphes. Nous considérons d’abord trois problèmes de coloration appelés coloration gloutonne, coloration pondérée et coloration pondérée impropre. Ensuite, nous traitons un problème de décision, appelé bon étiquetage d’arêtes, dont la définition a été motivée par le problème d’affectation de longueurs d’onde dans les réseaux optiques. La deuxième partie de cette thèse est consacrée à un paramètre d’optimisation des graphes appelé le nombre enveloppe (géodésique). La définition de ce paramètre est motivée par une extension aux graphes des notions d’ensembles et d’enveloppes convexes dans l’espace Euclidien. Enfin, nous présentons dans l’annexe d’autres travaux développés au cours de cette thèse, l’un sur les hypergraphes orientés Eulériens et Hamiltoniens et l’autre concernant les systèmes de stockage distribués
In this thesis, we study several problems of Graph Theory concerning Graph Coloring and Graph Convexity. Most of the results contained here are related to the computational complexity of these problems for particular graph classes. In the first and main part of this thesis, we deal with Graph Coloring which is one of the most studied areas of Graph Theory. We first consider three graph coloring problems called Greedy Coloring, Weighted Coloring and Weighted Improper Coloring. Then, we deal with a decision problem, called Good Edge-Labelling, whose definition was motivated by the Wavelength Assignment problem in optical networks. The second part of this thesis is devoted to a graph optimization parameter called (geodetic) hull number. The definition of this parameter is motivated by an extension to graphs of the notions of convex sets and convex hulls in the Euclidean space. Finally, we present in the appendix other works developed during this thesis, one about Eulerian and Hamiltonian directed hypergraphs and the other concerning distributed storage systems

APA, Harvard, Vancouver, ISO, and other styles

28

He, Weihua. "Cycles in graphs and arc colorings in digraphs." Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112352.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

29

Modrzejewski, Remigiusz. "Distribution et Stockage de Contenus dans les Réseaux." Phd thesis, Université Nice Sophia Antipolis, 2013. http://tel.archives-ouvertes.fr/tel-00917032.

Full text

Abstract:

Dans cette thèse, nous étudions divers problèmes dont l'objectif est de gérer la croissance d'internet plus efficacement. En effet celle-ci est très vive : 41% pour le pic en 2012. Afin de répondre aux défis posés par cette évolution aux divers acteurs du réseau, des protocoles de gestion et de communication plus intelligents sont nécessaires. Les protocoles de l'Internet furent conçus, point à point. Or, la part de la diffusion de média dans le trafic est prépondérante et en hausse tendancielle, et des projections indiquent qu'en 2016 80-90% du trafic sera engendré par de la diffusion vidéo. Cette divergence entraîne des inefficacités car les données parcourent plusieurs fois le réseau. Dans cette thèse, nous étudions comment tempérer cette inefficacité. Nos contributions sont organisées selon les couches et les phases de déploiement du réseau. Nous étudions le placement de caches lors de la conception du réseau. Ensuite, pour la gestion d'un réseau, nous regardons quand placer des appareils en veille, en utilisant un mécanisme de cache et en coopération avec des réseaux de distribution. Puis, au niveau de la couche application, nous étudions un problème de maintenance d'arbres équilibrés pour la diffusion de média. Enfin, nous analysons la probabilité de survie de données dans un système de sauvegarde distribuée. Notre travail se fonde à la fois sur des méthodes théoriques (Chaînes de Markov, Programmation Linéaire), mais aussi sur des outils empiriques tels que la simulation et l'expérimentation.

APA, Harvard, Vancouver, ISO, and other styles

30

Loeb, Sarah. "Extending List Colorings of Planar Graphs." Scholarship @ Claremont, 2011. http://scholarship.claremont.edu/hmc_theses/6.

Full text

Abstract:

In the study of list colorings of graphs, we assume each vertex of a graph has a specified list of colors from which it may be colored. For planar graphs, it is known that there is a coloring for any list assignment where each list contains five colors. If we have some vertices that are precolored, can we extend this to a coloring of the entire graph? We explore distance constraints when we allow the lists to contain an extra color. For lists of length five, we fix $W$ as a subset of $V(G)$ such that all vertices in $W$ have been assigned colors from their respective lists. We give a new, simplified proof where there are a small number of precolored vertices on the same face. We also explore cases where $W=\{u,v\}$ and $G$ has a separating $C_3$ or $C_4$ between $u$ and $v$.

APA, Harvard, Vancouver, ISO, and other styles

31

Esperet, Louis. "Distance-two colorings of graphs." Bordeaux 1, 2008. http://www.theses.fr/2008BOR13591.

Full text

Abstract:

Dans cette thèse, on s'intéresse en particulier à la coloration du carré des graphes planaires (deux sommets à distance au plus deux ont des couleurs distinctes) et à la coloration cyclique des graphes planaires (deux sommets incidents à la même face ont des couleurs distinctes). On montre un résultat général qui implique que deux conjectures importantes sur ces colorations (Wegner 1977 et Borodin 1984) sont vraies asymptotiquement. On s'intéresse également à d'autres colorations à distance deux, qui ont des liens (plus ou moins vagues) avec l'allocation de fréquences dans les réseaux radios, la théorie des jeux, la sociologie, et l'écologie.

APA, Harvard, Vancouver, ISO, and other styles

32

Labelle, François. "Graph embeddings and approximate graph coloring." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape3/PQDD_0031/MQ64386.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Montgomery, Bruce Lee. "Dynamic coloring of graphs." Morgantown, W. Va. : [West Virginia University Libraries], 2001. http://etd.wvu.edu/templates/showETD.cfm?recnum=2109.

Full text

Abstract:

Thesis (Ph. D.)--West Virginia University, 2001.
Title from document title page. Document formatted into pages; contains viii, 52 p. : ill. Vita. Includes abstract. Includes bibliographical references (p. 51).

APA, Harvard, Vancouver, ISO, and other styles

34

Berke, Robert. "Colorings and transversals of graphs." Zürich : ETH, 2008. http://e-collection.ethbib.ethz.ch/show?type=diss&nr=17797.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Harney, Isaiah H. "Colorings of Hamming-Distance Graphs." UKnowledge, 2017. http://uknowledge.uky.edu/math_etds/49.

Full text

Abstract:

Hamming-distance graphs arise naturally in the study of error-correcting codes and have been utilized by several authors to provide new proofs for (and in some cases improve) known bounds on the size of block codes. We study various standard graph properties of the Hamming-distance graphs with special emphasis placed on the chromatic number. A notion of robustness is defined for colorings of these graphs based on the tolerance of swapping colors along an edge without destroying the properness of the coloring, and a complete characterization of the maximally robust colorings is given for certain parameters. Additionally, explorations are made into subgraph structures whose identification may be useful in determining the chromatic number.

APA, Harvard, Vancouver, ISO, and other styles

36

Yahiaoui, Said. "Algorithmes et applications pour la coloration et les alliances dans les graphes." Thesis, Lyon 1, 2013. http://www.theses.fr/2013LYO10274.

Full text

Abstract:

Dans cette thèse, nous nous intéressons aux aspects algorithmiques et applications de deux problèmes de graphes, à savoir, la coloration et les alliances. La première partie concerne deux variantes de la coloration de graphes, la coloration Grundy et la coloration forte stricte. Nous commençons par l'étude du nombre Grundy des graphes réguliers. Nous donnons une condition fixe k, nous fournissons une condition nécessaire et suffisante pour que le nombre Grundy d'un graphe régulier soit au moins égal k. Nous caractérisons la classe des graphes cubiques (3-réguliers) pour laquelle le nombre Grundy est égal à 4, et nous présentons un algorithme linéaire pour déterminer le nombre Grundy d'un graphe cubique quelconque. Par ailleurs, en se basant sur la coloration forte stricte pour décomposer les arbres en petites composantes, nous présentons un nouvel algorithme pour l'appariement d'arbres étiquetés, non-ordonnés non-enracinés. Nous montrons que la distance calculée entre deux arbres est une pseudo-métrique. Nos expérimentations sur de larges bases synthétiques et des bases de données réelles confirment nos résultats analytiques et montrent que la distance proposée est précise et son algorithme est scalable. La seconde partie de cette thèse est consacrée aux alliances dans les graphes. Nous proposons un algorithme distribué autostabilisant pour la construction d'alliance offensive globale minimale dans un graphe arbitraire. Nous démontrons que cet algorithme converge sous le démon synchrone en temps linéaire. Ensuite, nous donnons le premier algorithme distribué autostabilisant pour le problème de l'alliance forte globale minimale dans un graphe quelconque. Nous prouvons que cet algorithme est polynomial sous le démon inéquitable distribué. Nous montrons par la suite, comment cet algorithme peut être adapté pour des généralisations du problème, comme la k-alliance forte et l'alliance forte pondérée. Enfin, en se basant sur les propriétés structurelles de l'alliance offensive, nous présentons une solution pour décentraliser le protocole de signalisation SIP. Ceci rend possible son déploiement dans un réseau mobile ad hoc
This thesis investigates the algorithmic aspects and applications of two graph problems, namely, colorings and alliances. In the first part, we focus on two variants of the proper vertex coloring, the Grundy coloring and the strict strong coloring. We start by the study of Grundy number for regular graphs. We give a sufficient condition for d-regular graphs with sufficiently large girth to have Grundy number equals d + 1. Then, using graph homomorphism, we obtain a necessary and sufficient condition for d-regular graphs to have Grundy number at least k. Moreover, we characterize cubic graphs (3-regular) for which the Grundy number is d + 1, and present a linear-time algorithm to determine the Grundy number of any arbitrary cubic graph. Subsequently, based on the strict strong coloring, we present an approach for the problem of matching labeled trees. Using this coloring, we propose a new algorithm to deterministically decompose a tree into small components. This leads to an efficient algorithm to measure an accurate distance between unrooted unordered labeled trees. The second part is devoted to the alliances in graphs. We first propose a linear-time self-stabilizing algorithm for the minimal global offensive alliance set problem, under the synchronous distributed scheduler. Then, we give the first self-stabilizing algorithm for the minimal global powerful alliance set problem in arbitrary graphs. Moreover, we show how this algorithm can be adapted to find the minimal global powerful k-alliance and the minimal weighted global powerful alliance sets. We prove that all these algorithms converge in polynomial-time under the unfair distributed scheduler. Finally, based on the structural properties of the offensive alliance, we propose a solution to decentralize the signaling protocol SIP. This enables SIP applications in mobile ad hoc networks

APA, Harvard, Vancouver, ISO, and other styles

37

Sahili, Amine El. "Colorations et orientations des graphes." Lyon 1, 1996. http://www.theses.fr/1996LYO10141.

Full text

Abstract:

La these est constituee de deux parties fonctions et line digraphes et chemins dans des graphes orientes n-chromatiques. Dans la premiere partie, nous donnons la definition des line digraphes. Nous discutons le probleme de la reconnaissance des graphes sousjacents des line digraphes. Chvatal et ebenegger ont demontre que ce probleme est np-complet. Nous remarquons que leur preuve suffit pour demontrer que le probleme reste np-complet si on se limite au line digraphes l(h), ou h est un digraphe dans lequel tout sommet a un degree interieur ou exterieur au plus un. Nous caracterisons ensuite ces graphes en rajoutant une condition supplementaire. Plusieurs applications sur des structures des fonctions sont donnees ensuite. Dans la deuxieme partie, nous partons de la question suivante: soit d une orientation d'un graphe n-chromatique. Quels sont les chemins orientes qu'on est sur de trouver dans d comme sous-digraphes. Nous traitons deux types particuliers de chemins: 1. Les chemins constitues par deux blocs 2. Les chemins antidirectes

APA, Harvard, Vancouver, ISO, and other styles

38

Moura, Phablo Fernando Soares. "Graph colorings and digraph subdivisions." Universidade de São Paulo, 2017. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23052017-100619/.

Full text

Abstract:

The vertex coloring problem is a classic problem in graph theory that asks for a partition of the vertex set into a minimum number of stable sets. This thesis presents our studies on three vertex (re)coloring problems on graphs and on a problem related to a long-standing conjecture on subdivision of digraphs. Firstly, we address the convex recoloring problem in which an arbitrarily colored graph G is given and one wishes to find a minimum weight recoloring such that each color class induces a connected subgraph of G. We show inapproximability results, introduce an integer linear programming (ILP) formulation that models the problem and present some computational experiments using a column generation approach. The k-fold coloring problem is a generalization of the classic vertex coloring problem and consists in covering the vertex set of a graph by a minimum number of stable sets in such a way that every vertex is covered by at least k (possibly identical) stable sets. We present an ILP formulation for this problem and show a detailed polyhedral study of the polytope associated with this formulation. The last coloring problem studied in this thesis is the proper orientation problem. It consists in orienting the edge set of a given graph so that adjacent vertices have different in-degrees and the maximum in-degree is minimized. Clearly, the in-degrees induce a partition of the vertex set into stable sets, that is, a coloring (in the conventional sense) of the vertices. Our contributions in this problem are on hardness and upper bounds for bipartite graphs. Finally, we study a problem related to a conjecture of Mader from the eighties on subdivision of digraphs. This conjecture states that, for every acyclic digraph H, there exists an integer f(H) such that every digraph with minimum out-degree at least f(H) contains a subdivision of H as a subdigraph. We show evidences for this conjecture by proving that it holds for some particular classes of acyclic digraphs.
O problema de coloração de grafos é um problema clássico em teoria dos grafos cujo objetivo é particionar o conjunto de vértices em um número mínimo de conjuntos estáveis. Nesta tese apresentamos nossas contribuições sobre três problemas de coloração de grafos e um problema relacionado a uma antiga conjectura sobre subdivisão de digrafos. Primeiramente, abordamos o problema de recoloração convexa no qual é dado um grafo arbitrariamente colorido G e deseja-se encontrar uma recoloração de peso mínimo tal que cada classe de cor induza um subgrafo conexo de G. Mostramos resultados sobre inaproximabilidade, introduzimos uma formulação linear inteira que modela esse problema, e apresentamos alguns resultados computacionais usando uma abordagem de geração de colunas. O problema de k-upla coloração é uma generalização do problema clássico de coloração de vértices e consiste em cobrir o conjunto de vértices de um grafo com uma quantidade mínima de conjuntos estáveis de tal forma que cada vértice seja coberto por pelo menos k conjuntos estáveis (possivelmente idênticos). Apresentamos uma formulação linear inteira para esse problema e fazemos um estudo detalhado do politopo associado a essa formulação. O último problema de coloração estudado nesta tese é o problema de orientação própria. Ele consiste em orientar o conjunto de arestas de um dado grafo de tal forma que vértices adjacentes possuam graus de entrada distintos e o maior grau de entrada seja minimizado. Claramente, os graus de entrada induzem uma partição do conjunto de vértices em conjuntos estáveis, ou seja, induzem uma coloração (no sentido convencional) dos vértices. Nossas contribuições nesse problema são em complexidade computacional e limitantes superiores para grafos bipartidos. Finalmente, estudamos um problema relacionado a uma conjectura de Mader, dos anos oitenta, sobre subdivisão de digrafos. Esta conjectura afirma que, para cada digrafo acíclico H, existe um inteiro f(H) tal que todo digrafo com grau mínimo de saída pelo menos f(H) contém uma subdivisão de H como subdigrafo. Damos evidências para essa conjectura mostrando que ela é válida para classes particulares de digrafos acíclicos.

APA, Harvard, Vancouver, ISO, and other styles

39

Mihalas, Stelian. "Graph dimension and related colorings /." The Ohio State University, 1999. http://rave.ohiolink.edu/etdc/view?acc_num=osu1488190109867877.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Jin, Yan. "Hybrid metaheuristic algorithms for sum coloring and bandwidth coloring." Thesis, Angers, 2015. http://www.theses.fr/2015ANGE0062/document.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

41

Fowler, Thomas George. "Unique coloring of planar graphs." Diss., Georgia Institute of Technology, 1998. http://hdl.handle.net/1853/30358.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Salavatipour, Mohammadreza. "On sum coloring of graphs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape3/PQDD_0023/MQ50369.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Sengupta, Rik. "List coloring in general graphs." Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/112878.

Full text

Abstract:

Thesis: S.M., Massachusetts Institute of Technology, Department of Mathematics, 2015.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 30-31).
In this thesis we explore some of the relatively new approaches to the problem of list-coloring graphs. This is a problem that has its roots in classical graph theory, but has developed an entire theory of its own, that uses tools from structural graph theory, probabilistic approaches, as well as heuristic and algorithmic approaches. This thesis details two approaches one can take to understand list-coloring and prove results for several classes of graphs; one of them is to use the idea of graph kernels, and the other is to look at list-edge-coloring. In this thesis we present the state-of-the-art research on these two problems. We begin by setting up definitions and preliminaries, and then go into each of these two topics in turn. Along the way we briefly mention some of the very new research on the topics, including some new approaches developed for the purpose of writing this thesis. We finish with a survey of some of the major open problems that still remain in the area.
by Rik Sengupta.
S.M.

APA, Harvard, Vancouver, ISO, and other styles

44

Kurt, Oguz. "On The Coloring of Graphs." The Ohio State University, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=osu1262287401.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Song, Zengmin. "Cycles and coloring in graphs." HKBU Institutional Repository, 2001. http://repository.hkbu.edu.hk/etd_ra/285.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Bazzaro, Fabrice. "Etiquetage de graphes : codage et coloration." Bordeaux 1, 2005. http://www.theses.fr/2005BOR12954.

Full text

Abstract:

Dans ce mémoire de thèse, nous nous intéressons à deux variantes d'étiquetage de graphes : l'étiquetage de distance et l'étiquetage avec contraintes tel que L(p, q)-étiquetage et l'étiquetage (d, 1)-total. L'étiquetage de distance est un codage du graphe permettant de calculer des distances. Nous nous sommes efforcés d'en définir un schéma pour les graphes de permutation. Pour cela, une étude sur la structure de cette famille a été effectuée. Dans cette optique, nous avons proposé une caractérisation de cette famille et défini un algorithme de reconnaissance dynamique. La seconde partie de notre travail s'est portée sur l'étiquetage (d,1)-total et le L(p,q)-étiquetage qui sont des problèmes liés à l'assignation de fréquences dans des réseaux d'émetteurs. Pour l'étiquetag (d,1)-total, nous obtenons des résultats optimaux sur la largeur de la bande de fréquence utilisée dans le cas des topologies planaires de grande maille et de grand degré maximum. Enfin, pour le L(p,q)-étiquetage une étude de complexité sur des étiquetages sans trou a été effectuée. Nous donnons la complexité de la décidabilité sur cet étiquetage dans les graphes quelconques suivant les valeurs des paramètres p et q. En effet, tous les graphes n'admettent pas de L(p,q)-étiquetage sans trou, le problème de décidabilité est donc primordial.

APA, Harvard, Vancouver, ISO, and other styles

47

Poon, Hoifung. "Coloring clique hypergraphs." Morgantown, W. Va. : [West Virginia University Libraries], 2000. http://etd.wvu.edu/templates/showETD.cfm?recnum=1494.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

McClain, Christopher. "Edge colorings of graphs and multigraphs." Columbus, Ohio : Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1211904033.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Casselgren, Carl Johan. "On some graph coloring problems." Doctoral thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-43389.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Bacak, Gökşen Ufuktepe Ünal. "Vertex Coloring of A Graph/." [s.l.] : [s.n.], 2004. http://library.iyte.edu.tr/tezler/master/matematik/T000416.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Coloriage de graphe'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles