The choice number of a graph G, denoted ch(G), is the minimum integer k such that for any assignment of lists of size k to the vertices of G, there is a proper colouring of G such that every vertex is mapped to a colour in its list. For general graphs, the choice number is not bounded above by a function of the chromatic number.In this thesis, we prove a conjecture of Ohba which asserts that ch(G) = χ(G) whenever |V (G)| ≤ 2χ(G) + 1. We also prove a strengthening of Ohba's Conjecture which is best possible for graphs on at most 3χ(G) vertices, and pose several conjectures related to our work. / Le nombre de choix d'un graphe G, noté ch(G), est le plus petit entier k tel que pour toute affectation de listes de taille k au sommets de G, il y a une coloration de G tel que chaque sommet de G est coloré par une couleur de sa liste. En général, le nombre de choix n'est pas borné supérieurement par une fonction du nombre chromatique.Dans cette thèse, nous démontrons une conjecture de Ohba qui affirme que ch(G) =χ(G) dès que |V (G)| ≤ 2χ(G) + 1. Nous démontrons aussi une version plus forte de la conjecture de Ohba qui est optimale pour les graphes ayant au plus 3χ(G) sommets, et énonçons plusieurs conjectures par rapport à nos travaux.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.119763 |
| Date | January 2013 |
| Creators | Noel, Jonathan |
| Contributors | Bruce Alan Reed (Internal/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 | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (Department of Mathematics and Statistics) |
| 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.0017 seconds