Let G be a graph and k be an integer greater than or equal to the chromatic number of G. The k-colouring graph of G is the graph whose vertices are k-colourings of G, with two colourings adjacent if they colour exactly one vertex differently. We explore the Hamiltonicity and connectivity of such graphs, with particular focus on the k-colouring graphs of complete multipartite graphs. We determine the connectivity of the k-colouring graph of the complete graph on n vertices for all n, and show that the k-colouring graph of a complete multipartite graph K is 2-connected whenever k is at least the chromatic number of K plus one. Additionally, we examine a conjecture that every connected k-colouring graph is 2-connected, and give counterexamples for k greater than or equal to 4. As our main result, we show that for all k greater than or equal to 2t, the k-colouring graph of a complete t-partite graph is Hamiltonian. Finally, we characterize the complete multipartite graphs K whose k-colouring graphs are Hamiltonian when k is the chromatic number of K plus one. / Graduate
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/5815 |
| Date | 23 December 2014 |
| Creators | Bard, Stefan |
| Contributors | MacGillivray, Gary |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web, http://creativecommons.org/publicdomain/zero/1.0/ |
Page generated in 0.0016 seconds