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.
","abstract_html":"<p>Let <em>G</em> be a graph. For <em>k</em> ≥ <em>d</em> ≥ 1, a <em>k</em>/<em>d</em> -coloring of <em>G</em> is a coloring <em>c</em> of vertices of <em>G</em> with colors 0, 1, 2, . . ., <em>k</em> - 1, such that <em>d</em> ≤ | <em>c</em>(<em>x</em>) - <em>c</em>(<em>y</em>) | ≤ <em>k</em> - <em>d</em>, whenever <em>xy</em> is an edge of <em>G</em>. We say that the circular chromatic number of <em>G</em>, denoted <em>χ<sub>c</sub></em>(<em>G</em>), is equal to the smallest <em>k</em>/<em>d</em> where a <em>k</em>/<em>d</em> -coloring exists. In [6], Pan and Zhu have given a function <em>μ</em>(<em>g</em>) that gives an upper bound for the circular-chromatic number for every <em>K</em><sub>4</sub>-minor-free graph <em>G<sub>g</sub></em> of odd girth at least <em>g</em>, <em>g</em> ≥ 3. In [7], they have shown that their upper bound in [6] can not be improved by constructing a sequence of graphs approaching <em>μ</em>(<em>g</em>) asymptotically. We prove that for every odd integer <em>g</em> = 2<em>k</em> + 1, there exists a graph <em>G<sub>g</sub></em> ∈ <em><b>G</b></em>/<em>K</em><sub>4</sub> of odd girth <em>g</em> such that <em>χ<sub>c</sub></em>(<em>G<sub>g</sub></em>) = μ(<em>g</em>) if and only if <em>k</em> is not divisible by 3. In other words, for any odd <em>g</em>, the question of attainability of μ(<em>g</em>) is answered for all <em>g</em> by our results. Furthermore, the proofs [6] and [7] are long and tedious. We give simpler proofs for both of their results.</p>","abstract_has_math":false,"creators":["Holt, Tracy Lance"],"institution":null,"degree_name":"MS (Master of Science)","degree_level":"Thesis - unrestricted","degree_discipline":"Mathematical Sciences","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2008,"date_issued":"2008-05-03T07:00:00Z","date_published":"2008-05-03T07:00:00Z","updated_at":"2026-07-24T02:21:03Z","subjects":["Graph Homomorphism","Circular Chromaitc Number","Circular Graphs","Graph Theory","Discrete Mathematics and Combinatorics","Mathematics","Physical Sciences and Mathematics"],"languages":[],"rights":["Copyright by the authors."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://dc.etsu.edu/etd/1916","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Holt, Tracy Lance"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2008-05-03T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematical Sciences"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis - unrestricted"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS (Master of Science)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graph Homomorphism","Circular Chromaitc Number","Circular Graphs","Graph Theory","Discrete Mathematics and Combinatorics","Mathematics","Physical Sciences and Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["Copyright by the authors."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://dc.etsu.edu/context/etd/article/3268/viewcontent/HoltT041308f.pdf","https://dc.etsu.edu/etd/1916"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.
"]},{"key":"dc:title","label":"Title","values":["On the Attainability of Upper Bounds for the Circular Chromatic Number of K4-Minor-Free Graphs."]}]}],"canonical_facts":{"dc:creator":["Holt, Tracy Lance"],"dc:date.issued":["2008-05-03T07:00:00Z"],"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.
"],"dc:identifier":["https://dc.etsu.edu/context/etd/article/3268/viewcontent/HoltT041308f.pdf","https://dc.etsu.edu/etd/1916"],"dc:rights":["Copyright by the authors."],"dc:subject":["Graph Homomorphism","Circular Chromaitc Number","Circular Graphs","Graph Theory","Discrete Mathematics and Combinatorics","Mathematics","Physical Sciences and Mathematics"],"dc:title":["On the Attainability of Upper Bounds for the Circular Chromatic Number of K4-Minor-Free Graphs."],"thesis:degree_discipline":["Mathematical Sciences"],"thesis:degree_level":["Thesis - unrestricted"],"thesis:degree_name":["MS (Master of Science)"]},"updated_at":"2026-07-24T02:21:03Z"}