#### Title

On the Attainability of Upper Bounds for the Circular Chromatic Number of *K*_{4}-Minor-Free Graphs.

#### Degree Name

MS (Master of Science)

#### Program

Mathematical Sciences

#### Date of Award

5-2008

#### Committee Chair or Co-Chairs

Yared Nigussie

#### Committee Members

Robert A. Beeler, Robert B. Gardner

#### Abstract

Let *G* be a graph. For *k* ≥ *d* ≥ 1, a *k*/*d* -coloring of *G* is a coloring *c* of vertices of *G* with colors 0, 1, 2, . . ., *k* - 1, such that *d* ≤ | *c*(*x*) - *c*(*y*) | ≤ *k* - *d*, whenever *xy* is an edge of *G*. We say that the circular chromatic number of *G*, denoted *χ _{c}*(

*G*), is equal to the smallest

*k*/

*d*where a

*k*/

*d*-coloring exists. In [6], Pan and Zhu have given a function

*μ*(

*g*) that gives an upper bound for the circular-chromatic number for every

*K*

_{4}-minor-free graph

*G*of odd girth at least

_{g}*g*,

*g*≥ 3. In [7], they have shown that their upper bound in [6] can not be improved by constructing a sequence of graphs approaching

*μ*(

*g*) asymptotically. We prove that for every odd integer

*g*= 2

*k*+ 1, there exists a graph

*G*∈

_{g}*/*

**G***K*

_{4}of odd girth

*g*such that

*χ*(

_{c}*G*) = μ(

_{g}*g*) if and only if

*k*is not divisible by 3. In other words, for any odd

*g*, the question of attainability of μ(

*g*) is answered for all

*g*by our results. Furthermore, the proofs [6] and [7] are long and tedious. We give simpler proofs for both of their results.

#### Document Type

Thesis - Open Access

#### Recommended Citation

Holt, Tracy Lance, "On the Attainability of Upper Bounds for the Circular Chromatic Number of *K*_{4}-Minor-Free Graphs." (2008). *Electronic Theses and Dissertations.* Paper 1916. http://dc.etsu.edu/etd/1916

#### Copyright

Copyright by the authors.