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
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.18201 |
| Date | January 2004 |
| Creators | Meagher, Conor John |
| Contributors | Bruce Alan Reed (Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.3465 seconds