Back to search

East Tennessee State University

On the Attainability of Upper Bounds for the Circular Chromatic Number of <em>K</em><sub>4</sub>-Minor-Free Graphs.

Abstract

dc:description.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 K4-minor-free graph Gg of odd girth at least 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 = 2k + 1, there exists a graph Gg ∈ G/K4 of odd girth g such that χc(Gg) = μ(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.

Degree

thesis:*
Name thesis:degree_name
MS (Master of Science)
Level thesis:degree_level
Thesis - unrestricted
Discipline thesis:degree_discipline
Mathematical Sciences
Year dc:date.issued
2008

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Holt, Tracy Lance

Subjects

dc:subject × 7

Rights

dc:rights
Statement dc:rights
  • Copyright by the authors.

Identifiers

dc:identifier.*
Repository record dc:identifier
https://dc.etsu.edu/etd/1916

Chain of custody

source
Harvested from
East Tennessee State University
Base URL
dc.etsu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Holt, Tracy Lance. On the Attainability of Upper Bounds for the Circular Chromatic Number of <em>K</em><sub>4</sub>-Minor-Free Graphs.. Thesis - unrestricted thesis, 2008. https://dc.etsu.edu/etd/1916