Auswahl der wissenschaftlichen Literatur zum Thema „Fractional colourings“

La décomposition des graphes fait référence au processus de décomposer un graphe complexe en composantes plus simples et plus petites, souvent dans le but d'analyser ou de résoudre des problèmes liés au graphe. Il s'agit d'un outil important pour représenter la structure globale et les propriétés d'une manière plus détaillée. Il est aussi également utile pour résoudre des problèmes impliquant la recherche de structures spécifiques dans un graphe. Il existe plusieurs types courants de techniques de décomposition de graphe largement utilisées en théorie des graphes et dans des domaines connexes, notamment la décomposition en arbres, la décomposition en blocs, la décomposition modulaire, la décomposition hiérarchique, etc. Cette thèse étudie deux types de décomposition de sommets d'un graphe : les colorations propres (décomposition en ensembles indépendants) et la Hamilton-connectivité (décomposition en chemins internement disjoints entre deux ensembles où les chemins couvrent tous les sommets du graphe)
The decomposition of graphs refers to the process of breaking down a complex graph into simpler, smaller components, often with the goal of analysing or solving problems related to the graph. It is an important tool to display the global structure and properties in a more fine-grained manner, and also useful in solving problems that involve finding specific structures in a graph. There are several common types of graph decomposition techniques that are widely used in graph theory and related fields, including tree decomposition, block decomposition, modular decomposition, hierarchical decomposition, etc. This thesis studies two kinds of vertex decomposition of a graph: proper colourings (decomposition into independent sets) and Hamilton-connectivity (decomposition into internally-disjoint paths between two sets where the paths cover all the vertices of graphs)

Many problems which seek to schedule, sequence, or time-table a set of events subject to given constraints can be modelled as graph colouring problems. In this thesis, we study the edge and total colouring problems which, like all NP problems, can be formulated as integer programs and subjected to a two-pronged attack: we first solve the fractional relaxation and then use this solution to solve or obtain an approximation of the solution of the integer program. We focus on the complexity of solving the fractional relaxations of the integer programs for the edge and total colouring problems. For each ε > 0, we give a linear time algorithm which determines the fractional chromatic index of a graph $G$ with maximum degree at least ε|G|. For graphs with large maximum degree, this improves on Padberg and Rao's polynomial time algorithm to determine the fractional chromatic index for general graphs. Both algorithms rely on a theorem of Edmonds showing that the fractional chromatic index of a graph is determined by its maximum degree and overfull subgraphs. Our algorithm exploits the fact that overfull subgraphs are related to small cuts in a graph and have simple intersection patterns when the maximum degree is large. The complexity of determining the fractional total colouring number is currently unresolved. We focus on graphs with large maximum degree, applying the very successful techniques for fractional edge colouring to fractional total colouring. We characterize graphs with maximum degree Δ whose fractional total colouring number is Δ + 2, sharpening a result of Kilakos and Reed who showed it is between Δ + 1 and Δ+2. We show graphs whose fractional total colouring number is less than Δ + 2 have a special fractional vertex colouring which extends to a fractional total colouring using less than Δ + 2 colours. We extend these ideas by giving necessary conditions a fractional vertex ß-colouring must satisfy to be extendable to a fractional total ß-colouring. We conjecture these conditions are sufficient when G satisfies Δ > ½|G|. We verify a special case of this conjecture by giving a polynomial time algorithm which constructs an optimal fractional total colouring of a graph G with maximum degree at least ¾|G| and containing no overfull subgraphs.
De nombreux problèmes qui consistent à programmer, ordonner, ou encore planifier un ensemble d'événements étant données des contraintes peuvent être modilisés par un probème de coloriage de graphe. Dans cette thèse, nous étudions les problèmes du coloriage d'arêtes et du coloriage total, qui comme tous les problèmes NP, peuvent être formulés sous forme de programmation entière, et traités avec une approche en deux temps: on résoud d'abord la relaxation fractionnaire du programme entier, puis on utilise la solution du programme relaché pour déterminer ou approximer la solution du programme entier. Nous nous concentrons sur la complexité de la relaxation fractionnaire pour les problèmes du coloriage d'arêtes et du coloriage total.Pour tout ε > 0, nous donnons un algorithme linéaire qui détermine l'indice chromatique fractionnaire d'un graphe $G$ dont le degré maximal est au moins ε|G|. Pour les graphes dont le degré maximum est grand, ceci améliore l'algorithme polynomial de Padberg et Rao pour l'indice chromatique fractionnaire. Les deux algorithmes reposent sur un théorème dû à Edmonds qui montre que l'indice chromatique fractionnaire est déterminé par le degré maximum et les sous-graphes overfull. Notre algorithme exploite le fait que les sous-graphes overfull sont reliés aux petites coupes, et ont des motifs d'intersections simples lorsque le degré maximum est grand. La complexité du problème de coloriage total fractionnaire est toujours inconnue. Nous nous concentrons sur les graphes dont le degré maximum est grand, et appliquons au coloriage total fractionnaire les le techniques qui se sont avérées fructueuses pour le problème de coloriage d'arêtes. Nous charactérisons les graphes dont le degré maximum est Δ, et dont le nombre chromatique total fractionnaire est Δ+2, ce qui améliore un résultat de Kilakos et Reed qui ont montré qu'il est compris entre Δ+1 et Δ+2. Nous montrons que les graphes dont le nombre chromatique total fractionnaire est moins de Δ+2 possèdent un coloriage fractionnaire des noeuds qui s'étend en un coloriage total fractionnaire utilisant moins de Δ+2 couleurs. Nous généralisons ces idées en donnant des conditions nécéssaires que doit remplir un ß-coloriage des noeuds pour pouvoir être étendu en un ß-coloriage total fractionnaire. Nous conjecturons que ces conditions sont suffisantes lorsque Δ > ½|G|. Nous vérifions un cas particulier de cette conjecture en concevant un algorithme polynomial qui construit un coloriage total fractionnaire pour un graphe G dont le degré maximum est au moins ¾|G| et qui ne contient pas de sous-graphe overfull.

Although a considerable body of material exists concerning the colouring of graphs, there is much less on overlap colourings. In this thesis, we investigate the colouring of certain families of graphs.

A total colouring is the assignment of a colour to each vertex and edge of a graph such that no adjacent vertices or incident edges receive the same colour and no edge receives the same colour as one of its endpoints. If we formulate the problem of finding the total chromatic number as an integer program, we can consider the fractional relaxation known as fractional total colouring. In this thesis we present an algorithm for computing the fractional total chromatic number of a graph, which runs in polynomial time on average. We also present an algorithm that asymptotically almost surely computes the fractional total chromatic number of $G_{n,p}$ for all values of $p$.
Une coloration totale d’un graphe est le coloration des arêtes et des sommets telle que deux sommets adjacents ont des couleurs différentes, deux arêtes incidentes ont des couleurs différentes, et une arête a une couleur différente de celles des ses extrémités. Si nous formulons le problème de trouver le nombre chromatique total comme un programme linéaire entier, nous pouvons considérer la relaxation connue comme la coloration totale fractionnaire. Dans cette thèse nous présentons un algorithme pour calculer le nombre chromatique total d’un graphe en temps polynomial en moyenne. Nous présentons aussi un algorithme qui calcule asymptotiquement presque sûrement le nombre chromatique total de $G_{n,p}$ pour toute valeur de $p$. fr