published_or_final_version / abstract / Mathematics / Master / Master of Philosophy

M.Sc. / In this dissertation we study two types of colourings, namely line-distinguishing colourings and harmonious colourings. A line-distinguishing colouring of a graph G is a k-colouring of the vertices of G such that no two edges have the same colour. The line-distinguishing chromatic number G is defined as the smallest k such that G has a line-distinguishing k-colouring. A harmonious colouring of a graph G is a proper k-colouring of the vertices of G such that no two edges have the same colour, i.e. no two adjacent vertices can have the same colour. The harmonious chromatic number hG is defined as the smallest k such that G has a line-distinguishing k-colouring. In Chapter 0 we discuss some of the terminology and definitions used later on in our study. In Chapter 1 we introduce line-distinguishing colourings and consider the line-distinguishing chromatic number of certain familiar classes of graphs such as trees, paths, cycles and complete graphs. We also consider graphs with line-distinguishing chromatic number G equal to the usual chromatic number G, and we compare G with the chromatic index G of a graph. In Chapter 2 we mostly discuss minimal line-distinguishing (MLD) colourings. We consider minimal line-distinguishing colourings and graphs of diameter two as well as classes of regular MLD-colourable graphs. We also introduce the concept of distance regular graphs and discuss minimal line-distinguishing colourings in these graphs. In Chapter 3 we introduce a new parameter, namely the upper line-distinguishing chromatic number H G of a graph. We investigate H G for paths and cycles, and consider graphs with small upper line-distinguishing chromatic numbers. In Chapter 4 we consider the second type of colouring studied in this dissertation, namely harmonious colourings. We define the harmonious chromatic number hG and determine hG for certain classes of graphs such as paths, trees, cycles and complete graphs. In Chapter 5 we discuss upper and lower bound for hG. In Chapter 6 we discuss the upper harmonious chromatic number HG of a graph, and we determine HG for paths and cycles. We also consider graphs satisfying HG  G  1. The purpose of this study is to compile a resource which will give a thorough and well-integrated background on line-distinguishing and harmonious colourings. It is also intended to lay the groundwork for further doctoral studies in the field of colourings.

Thesis (Ph. D.)--Lehigh University, 2006. / Includes vita. Includes bibliographical references (leaf 86).

Thesis (M. Phil.)--University of Hong Kong, 2007. / Title proper from title frame. Also available in printed format.

Thesis (Ph. D.)--University of Iowa, 2007. / Supervisor: Sriram Pemmaraju. Includes bibliographical references (leaves 142-147).

Thomassen proved that there are only finitely many 6-critical graphs embeddable on a fixed surface. He also showed that planar graphs are 5-list-colorable. This thesis develops new techniques to prove general theorems for 5-list-coloring graphs embedded in a fixed surface. Indeed, a general paradigm is established which improves a number of previous results while resolving several open conjectures. In addition, the proofs are almost entirely self-contained. In what follows, let S be a fixed surface, G be a graph embedded in S and L a list assignment such that, for every vertex v of G, L(v) has size at least five. First, the thesis provides an independent proof of a theorem of DeVos, Kawarabayashi and Mohar that says if G has large edge-width, then G is 5-list-colorable. Moreover, the bound on the edge-width is improved from exponential to logarithmic in the Euler genus of S, which is best possible up to a multiplicative constant. Second, the thesis proves that there exist only finitely many 6-list-critical graphs embeddable in S, solving a conjecture of Thomassen from 1994. Indeed, it is shown that the number of vertices in a 6-list-critical graph is at most linear in genus, which is best possible up to a multiplicative constant. As a corollary, there exists a linear-time algorithm for deciding 5-list-colorability of graphs embeddable in S. Furthermore, we prove that the number of L-colorings of an L-colorable graph embedded in S is exponential in the number of vertices of G, with a constant depending only on the Euler genus g of S. This resolves yet another conjecture of Thomassen from 2007. The thesis also proves that if X is a subset of the vertices of G that are pairwise distance Omega(log g) apart and the edge-width of G is Omega(log g), then any L-coloring of X extends to an L-coloring of G. For planar graphs, this was conjectured by Albertson and recently proved by Dvorak, Lidicky, Mohar, and Postle. For regular coloring, this was proved by Albertson and Hutchinson. Other related generalizations are examined.

Hajós conjectured that, for any positive integer k, every graph containing no K_(k+1)-subdivision is k-colorable. This is true when k is at most three, and false when k exceeds six. Hajós' conjecture remains open for k=4,5. We will first present some known results on Hajós' conjecture. Then we derive a result on the structure of 2-connected graphs with no cycle through three specified vertices. This result will then be used for the proof of the main result of this thesis. We show that any possible counterexample to Hajós' conjecture for k=4 with minimum number of vertices must be 4-connected. This is a step in an attempt to reduce Hajós' conjecture for k=4 to the conjecture of Seymour that any 5-connected non-planar graph contains a K_5-subdivision.

Thesis (Ph. D.)--University of Wisconsin--Madison, 1982. / Typescript. Vita. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references (leaves 225-232).

In this paper, we introduce two new variations on the computable chromatic number: the computable list chromatic number and the computable coloring number. We show that, just as with the non-computable versions, the computable chromatic number is always less than or equal to the computable list chromatic number, which is less than or equal to the computable coloring number.We investigate the potential differences between the computable and non-computable chromatic, list chromatic, and coloring numbers on computable graphs. One notable example is a computable graph for which the coloring number is 2, but the computable chromatic number is infinite.

No description available.