Title page for etd-0014114-151402


[Back to Results | New Search]

URN etd-0014114-151402
Author Che-Yu Lin
Author's Email Address showming.lin@gmail.com
Statistics This thesis had been viewed 5348 times. Download 930 times.
Department Applied Mathematics
Year 2013
Semester 1
Degree Ph.D.
Type of Document
Language English
Title The circular chromatic numbers of line graphs and total graphs
Date of Defense 2013-11-24
Page Count 118
Keyword
  • line graph
  • circular colouring
  • circular chromatic index
  • circular total chromatic number
  • total graph
  • Abstract A circular r-colouring of a graph G is a mapping c : V (G) → [0, r) such that for any two adjacent vertices x and y, 1 ≤ |c(x) − c(y)| ≤ r−1. The circular chromatic number of G is χc(G) = inf{r : G has a circular r-colouring}.
    A circular r-edge-colouring of a graph G is a circular r-colouring of its line graph L(G). The circular chromatic index, written χ′c(G), is defined by χ′c(G) = χc(L(G)). It is known that for r ∈ (2, 3], there is a graph G with χ′c(G) = r if and only if r = 2 + 1/k for k ∈ N. In [23], Lukot’ka and Maz´ak proved that for any rational r ∈ (3, 10/3), there is a finite graph G with χ′c(G) = r. We prove that if k ≥ 3 is an odd integer, then for any rational r ∈ (k, k + 1/4), there is a finite graph G with χ′c(G) = r (Corollary 3.1.3); if k ≥ 4 is an even integer, then for any rational r ∈ (k, k + 1/6), there is a finite graph G with χ′
    c(G) = r (Corollary 3.1.4).
    A circular r-total-colouring of a graph G is a circular r-colouring of its total graph T(G). The circular total chromatic number, written χ′′c(G), is defined by χ′′c (G) = χc(T(G)). In [10], it was proved that for r ∈ (3, 4], there is a graph G with χ′′c (G) = r if and only if r = 3 + 1/k for k ∈ N. We prove that for any integer n ≥ 5 and any rational r ∈ (n, n + 1/3), there is a finite graph G with χ′′c (G) = r (Theorem 3.2.2).
    Advisory Committee
  • Ko-Wei Lih - chair
  • D. J. Guan - co-chair
  • Gerard J. Chang - co-chair
  • Sen-Peng Eu - co-chair
  • Tsai-Lien Wong - co-chair
  • Yeong-Nan Yeh - co-chair
  • Hong-Gwa Yeh - co-chair
  • Li-Da Tong - co-chair
  • Xuding Zhu - advisor
  • Files
  • etd-0014114-151402.pdf
  • indicate access worldwide
    Date of Submission 2014-01-14

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys