A coloring of a graph is an assignment of colors to its vertices so that no
two adjacent vertices are given the same color. The chromatic number of a
graph is the least number of colors needed to color all of its vertices. Graph
coloring problems can be applied to many real world applications, such as
scheduling and register allocation. Computationally, the decision problem
of whether a general graph is m-colorable is NP-complete for m ≥ 3.
The graph studied in this thesis is a well-known combinatorial object,
the k-dimensional hypercube, Qk. The hypercube itself is 2-colorable for all
k; however, coloring the square of the cube is a much more interesting problem.
This is the graph in which the vertices are binary vectors of length k,
and two vertices are adjacent if and only if the Hamming distance between
the two vectors is at most 2.
Any color class in a coloring of Q2k is a binary (k;M, 3) code. This thesis
will begin with an introduction to binary codes and their structure. One
of the most fundamental combinatorial problems is finding optimal binary
codes, that is, binary codes with the maximum cardinality satisfying a specified
length and minimum distance. Many upper and lower bounds have
been produced, and we will analyze and apply several of these. This leads
to many interesting results about the chromatic number of the square of the
cube.
The smallest k for which the chromatic number of Q2k is unknown is
k = 8; however, it can be determined that this value is either 13 or 14.
Computational approaches to determine the chromatic number of Q28 were
performed. We were unable to determine whether 13 or 14 is the true value;
however, much valuable insight was learned about the structure of this graph
and the computational difficulty that lies within. Since a 13-coloring of Q28
must have between 9 and 12 color classes being (8; 20; 3) binary codes, this
led to a thorough investigation of the structure of such binary codes.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:BVAU.2429/2809 |
| Date | 11 1900 |
| Creators | Rix, James Gregory |
| Publisher | University of British Columbia |
| 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 |
Page generated in 0.0019 seconds