In this thesis we give two different proofs of the result chromatic number of a special graph is 4. The first proof is derived by analysing the structure of the special graph. The second proof is a method which was first studied in [1].

This thesis constructs special graphs with given circular chromatic numbers or circular flow numbers. Suppose $G=(V,E)$ is a graph and $rgeq 2$ is a real number. An $r$-coloring of a graph $G$ is a mapping $f:V ightarrow [0,r)$ such that for any adjacent vertices $x,y$ of $G$, $1leq |f(x)-f(y)|leq r-1$. The circular chromatic number $chi_c(G)$ is the least $r$ for which there exists an $r$-coloring of $G$. The circular chromatic number was introduced by Vince in 1988 in cite{vince}, where the parameter is called the {em star chromatic number} and denoted by $chi^*(G)$. Vince proved that for any rational number $k/dgeq 2$ there is a graph $G$ with $chi_c(G)=k/d$. In this thesis, we are interested in the existence of special graphs with given circular chromatic numbers. A graph $H$ is called a minor of a graph $G$ if $H$ can be obtained from $G$ by deleting some vertices and edges, and contracting some edges. A graph $G$ is called $H$-minor free if $H$ is not a minor of G. The well-known Hadwiger's conjecture asserts that for any positive integer $n$, any $K_n$-minor free graph $G$ is $(n-1)$-colorable. If this conjecture is true, then for any $K_n$-minor free graph $G$, we have $chi_c(G)leq n-1$. On the other hand, for any graph $G$ with at least one edge we have $chi_c(G)geq 2$. A natural question is this: Is it true that for any rational number $2leq rleq n-1$, there exist a $K_n$-minor free graph $G$ with $chi_c(G)=r$? For $n=4$, the answer is ``no". It was proved by Hell and Zhu in cite{hz98} that if $G$ is a $K_4$-minor free graph then either $chi_c(G)=3$ or $chi_c(G)leq 8/3$. So none of the rational numbers in the interval $(8/3,3)$ is the circular chromatic number of a $K_4$-minor free graph. For $ngeq 5$, Zhu cite{survey} proved that for any rational number $rin[2,n-2]$, there exists a $K_n$-minor free graph $G$ with $chi_c(G)=r$. The question whether there exists a $K_n$-minor free graph $G$ with $chi_c(G)=r$ for each rational number $rin(n-2,n-1)$ remained open. In this thesis, we answer this question in the affirmative. For each integer $ngeq 5$, for each rational number $rin[n-2,n-1]$, we construct a $K_n$-minor free graph $G$ with $chi_c(G)=r$. This implies that for each $ngeq 5$, for each rational number $rin[2,n-1]$, there exists a $K_n$-minor free graph $G$ with $chi_c(G)=r$. In case $n=5$, the $K_5$-minor free graphs constructed in this thesis are actually planar graphs. So our result implies that for each rational number $rin[2,4]$, there exists a planar graph $G$ with $chi_c(G)=r$. This result was first proved by Moser cite{moser} and Zhu cite{3-4}. To be precise, Moser cite{moser} proved that for each rational number $rin[2,3]$, there exist a planar graph $G$ with $chi_c(G)=r$, and Zhu cite{3-4} proved that for each rational number $rin[3,4]$, there exists a planar graph $G$ with $chi_c(G)=r$. Moser's and Zhu's proofs are quite complicated. Our construction is conceptually simpler. Moreover, for $ngeq 5$, $K_n$-minor free graphs, including the planar graphs are constructed with a unified method. For $K_4$-minor free graphs, although Hell and Zhu cite{hz98} proved that there is no $K_4$-minor free graph $G$ with $chi_c(G)in (8/3,3)$. The question whether there exists a $K_4$-minor free graph $G$ with $chi_c(G)=r$ for each rational number $rin[2,8/3]$ remained open. This thesis solves this problem: For each rational number $rin[2,8/3]$, we shall construct a $K_4$-minor free $G$ with $chi_c(G)=r$. This thesis also studies the relation between the circular chromatic number and the girth of $K_4$-minor free graphs. For each integer $n$, the supremum of the circular chromatic number of $K_4$-minor free graphs of odd girth (the length of shortest odd cycle) at least $n$ is determined. It is also proved that the same bound is sharp for $K_4$-minor free graphs of girth $n$. By a classical result of ErdH{o}s, for any positive integers $l$ and $n$, there exists a graph $G$ of girth at least $l$ and of chromatic number $n$. Using probabilistic method, Zhu cite{unique} proved that for each integer $l$ and each rational number $rgeq 2$, there is a graph $G$ of girth at least $l$ such that $chi_c(G)=r$. Construction of such graphs for $rgeq 3$ was given by Nev{s}etv{r}il and Zhu cite{nz}. The question of how to construct large girth graph $G$ with $chi_c(G)=r$ for given $rin(2,3)$ remained open. In this thesis, we present a unified method that constructs, for any $rgeq 2$, a graph $G$ of girth at least $l$ with circular chromatic number $chi_c(G) =r$. Graphs $G$ with $chi_c(G)=chi(G)$ have been studied extensively in the literature. Many families of graphs $G$ are known to satisfy $chi_c(G)=chi(G)$. However it remained as an open question as how to construct arbitrarily large $chi$-critical graphs $G$ of bounded maximum degree with $chi_c(G)=chi(G)$. This thesis presents a construction of such graphs. The circular flow number $Phi_c(G)$ is the dual concept of $chi_c(G)$. Let $G$ be a graph. Replace each edge $e=xy$ by a pair of opposite arcs $a=overrightarrow{xy}$ and $a^{-1}=overrightarrow{yx}$. We obtain a symmetric directed graph. Denote by $A(G)$ the set of all arcs of $G$. A chain is a mapping $f:A(G) ightarrow I!!R$ such that for each arc $a$, $f(a^{-1})=-f(a)$. A flow is a chain such that for each subset $X$ of $V(G)$, $sum_{ain[X,ar{X}]}f(a)=0$, where $[X,ar{X}]$ is the set of all arcs from $X$ to $V-X$. An $r$-flow is a flow such that for any arc $ain A(G)$ , $1leq |f(a)| leq r-1$. The circular flow number of $G$ is $Phi_c(G)=mbox{ inf}{r: G mbox{ admits a } rmbox{-flow}}$. It was conjectured by Tutte that every graph $G$ has $Phi_c(G)leq 5$. By taking the geometrical dual of planar graphs, Moser's and Zhu's results concerning circular chromatic numbers of planar graphs imply that for each rational number $rin[2,4]$, there is a graph $G$ with $Phi_c(G)=r$. The question remained open whether for each $rin(4,5)$, there exists a graph $G$ with $Phi_c(G)=r$. In this thesis, for each rational number $rin [4,5]$, we construct a graph $G$ with $Phi_c(G)=r$.

In (J Graph Theory 33 (2000), 14-24), Hell and Zhu proved that if a series-parallel graph G has girth at least 2⌊(3k-1)/2⌋, then χc(G)≤4k/(2k-1). In (J Graph Theory 33 (2000), 185-198), Chien and Zhu proved that the girth condition given in (J Graph Theory 33 (2000), 14-24) is sharp. Short proofs of both results are given in this note.

During S phase of the cell cycle, newly synthesized histones are acetylated in the cytoplasm in patterns specific to DNA replication. Once incorporated into nucleosomes, these histones are rapidly deacetylated by enzymes known as histone deacetylases. Though common in all organisms, the significance of this molecular mechanism is not fully understood. Homologous to HDAC6 in humans and HDA1 in budding yeast, Tetrahymena histone deacetylase 2 (Thd2) has been identified as the only known histone deacetylase that performs this task in the unicellular eukaryote Tetrahymena thermophila. Localizing to the transcriptionally inactive germline nucleus, the micronucleus, Thd2 has been found to deacetylate histones H3 and H4 at K9 and/or K14. In order to gain further insight into the role of deposition-related deacetylation in chromatin maturation, the micronuclear morphology and modification status of H3K27, a known marker for heterochromatin in several eukaryotes, were examined in both vegetative and synchronized complete Δthd2 mutant cells. Immunofluorescence microscopy, DAPI staining and a western blot analysis revealed abnormal phenotypes and the conservation of H3K27 methylation in the absence of Thd2. These findings further indicate a role for Thd2 in the maintenance of chromatin structure and suggest the possibility of another mechanism required for deacetylation at H2K27. Essentially, this demonstrates the importance of deposition-related histone deacetylation in chromatin maturation after DNA replication and further maintenance of chromatin domains.

El principal objectiu d'aquest treball de tesi és tractar el problema de la representació de la textura en color des del punt de vista de la visió per computador. L'extensió dels mètodes classics de processament de textura per imatges en nivells de grisos als canals d'una imatge color no assegura resultats semblants als de la percepció humana en aquesta tasca. Els mecanismes d'inducció cromàtica del sistema visual humà, estudiats en psicofísica, són fonamentals en la dependència que crea l'entorn en la percepció del color. La inducció cromàtica inclou dos efectes complementaris: l'assimilació i el contrast cromàtic. Mentre el primer ja ha estat mesurat des de la psicofísica i extés a la visió per computador, molts aspectes del segon encara queden per fer. La contribució principal d'aquesta tesi és la definició d'un operador computacional que simula el fenòmen del contrast cromàtic i que té un comportament coherent amb el del sistema visual humà en diferents problemes de la percepcció de la textura en color, ja que permet enfatitzar les diferències de color en distribucions que són quasibé unimodals i així millorar la segmentació de les regions de color. El problema que encara queda obert és la realització de mesures psicofísiques pels paràmetres de l'operador, tal com es va fer amb l's-cielab per al procés d'assimilació.La definició de representacions computacionals de textura i color perceptuals és un objectiu de gran importància en els problemes d'inspecció automàtica de superfícies en els que els dispositius de la colorimetria clàssica no permeten donar bones mesures d'aparença de color. La segona contribució de la tesi defineix una representació computacional basada en mesures globals de color incloent-hi l'assimilació de color i mesures locals de les propietats de les regions segmentades considerant el contrast cromàtic. Aquesta representació és aplicada a la classificació de gres porcelànic.Tenint en compte que s'han de realitzar mesures molt acurades de petites diferències, s'ha dedicat una part d'aquest treball a l'adquisició d'imatges en color, i en concret a aconseguir bones propietats de constància de color. En aquest sentit, la darrera contribució de la tesi és la definició d'un algorisme de contància de color en línea per a una càmera lineal d'alta precisió de color. Aquest mètode s'ha basat en el model lineal diagonal de constància de color prèviament garantit amb una transformació que canvia les propietats de la sensibilitat de la càmera. / The main goal of this thesis is to deal with the colour texture representation problem from a computer vision point of view. It is easy to demonstrate that the extension of classical grey level methods for texture processing to the three channels of the corresponding colour texture does not succeed in having a human-like behaviour on this visual task. Chromatic induction mechanisms of the human visual system, which have been widely studied in psychophysics, play an important role on the dependency of the colour perception from its surround. Chromatic induction includes two complementary effects: chromatic assimilation and chromatic contrast. While the former has been psychophysically measured and lately extended to computer vision, some aspects on the last one still remain to be measured. The main contribution of this thesis is a computational operator that simulates the contrast induction phenomena that has demonstrated a coherent behaviour on different texture colour perception problems, since it allows to emphasise colour differences on almost-unimodal colour distributions and consequently improving the segmentation of colour regions. An open problem that will remain open from this work is the psychophysical measurement of the operator parameters, in the same sense as it was done with the s-cielab for the assimilation process.A perceptually consistent colour texture computational representation is a goal of extreme importance in automatic colour-textured surface inspection problems, where the classic colorimetric tools does not succeed in given good colour appearance measurements. In this scope, a second contribution is a colour-texture representation based on global colour features considering colour assimilation and local features based on properties of colour blobs considering colour contrast. This representation is applied to an automatic tile classification problem.Since an important accuracy is needed to measure such small differences, we have devoted a great part of this work to the colour acquisition issue, and to the problem of achieving good colour constancy properties on the acquired images. In this sense, a last contribution of this work has been to define an on-line colour constancy algorithm for a high colour precision scan line camera based on a diagonal linear colour constancy model previously guaranteed by linear transform changing the camera sensitivity properties.

In this thesis we take a specialized approach to edge-colouring by focusing exclusively on multigraphs with high chromatic index. The bulk of our results can be classified into three categories. First, we prove results which aim to characterize those multigraphs achieving known upper bounds. For example, Goldberg's Theorem says that χ'≤ Δ+1+(Δ-2}/(g₀+1) (where χ' denotes chromatic index, Δ denotes maximum degree, and g₀ denotes odd girth). We characterize this bound by proving that for a connected multigraph G, χ'= Δ+1+(Δ-2}/(g₀+1) if and only if G=μC_g₀ and (g₀+1)|2(μ-1) (where μ denotes maximum edge-multiplicity). Our second category of results are new upper bounds for chromatic index in multigraphs, and accompanying polynomial-time edge-colouring algorithms. Our bounds are all approximations to the famous Seymour-Goldberg Conjecture, which asserts that χ'≤ max{⌈ρ⌉, Δ+1} (where ρ=max{(2|E[S]|)/(|S|-1): S⊆V, |S|≥3 and odd}). For example, we refine Goldberg's classical Theorem by proving that χ'≤ max{⌈ρ⌉, Δ+1+(Δ-3)/(g₀+3)}. Our third category of results are characterizations of high chromatic index in general, with particular focus on our approximation results. For example, we completely characterize those multigraphs with χ'> Δ+1+(Δ-3)/(g₀+3). The primary method we use to prove results in this thesis is the method of Tashkinov trees. We first solidify the theory behind this method, and then provide general edge-colouring results depending on Tashkinov trees. We also explore the limits of this method, including the possibility of vertex-colouring graphs which are not line graphs of multigraphs, and the importance of Tashkinov trees with regard to the Seymour-Goldberg Conjecture.

In this thesis we take a specialized approach to edge-colouring by focusing exclusively on multigraphs with high chromatic index. The bulk of our results can be classified into three categories. First, we prove results which aim to characterize those multigraphs achieving known upper bounds. For example, Goldberg's Theorem says that χ'≤ Δ+1+(Δ-2}/(g₀+1) (where χ' denotes chromatic index, Δ denotes maximum degree, and g₀ denotes odd girth). We characterize this bound by proving that for a connected multigraph G, χ'= Δ+1+(Δ-2}/(g₀+1) if and only if G=μC_g₀ and (g₀+1)|2(μ-1) (where μ denotes maximum edge-multiplicity). Our second category of results are new upper bounds for chromatic index in multigraphs, and accompanying polynomial-time edge-colouring algorithms. Our bounds are all approximations to the famous Seymour-Goldberg Conjecture, which asserts that χ'≤ max{⌈ρ⌉, Δ+1} (where ρ=max{(2|E[S]|)/(|S|-1): S⊆V, |S|≥3 and odd}). For example, we refine Goldberg's classical Theorem by proving that χ'≤ max{⌈ρ⌉, Δ+1+(Δ-3)/(g₀+3)}. Our third category of results are characterizations of high chromatic index in general, with particular focus on our approximation results. For example, we completely characterize those multigraphs with χ'> Δ+1+(Δ-3)/(g₀+3). The primary method we use to prove results in this thesis is the method of Tashkinov trees. We first solidify the theory behind this method, and then provide general edge-colouring results depending on Tashkinov trees. We also explore the limits of this method, including the possibility of vertex-colouring graphs which are not line graphs of multigraphs, and the importance of Tashkinov trees with regard to the Seymour-Goldberg Conjecture.

Color plays a vitally important role in the world we live in. It surrounds us everywhere we go. Achromatic life, restricted to black, white and grey, is extremely dull. Color fascinates artists, for it adds enormously to aesthetic appreciation, directly invoking thoughts, emotions and feelings. Color fascinates scientists. For decades, scientists in color imaging, printing and digital photography have striven to satisfy increasing demands for accuracy in color reproduc- tion. Fluorescence is a very common phenomenon observed in many objects such as gems and corals, writing paper, clothes, and even laundry detergent. Traditional color imaging algo- rithms exclude fluorescence by assuming that all objects have only an ordinary reflective com- ponent. The first part of the thesis shows that the color appearance of an object with both reflective and fluorescent components can be represented as a linear combination of the two components. A linear model allows us to separate the two components using independent component analysis (ICA). We can then apply different algorithms to each component, and combine the results to form images with more accurate color. Displaying color images accurately is as important as reproducing color images accurately. The second part of the thesis presents a new, practical model for displaying color images on self-luminous displays such as LCD monitors. It shows that the model accounts for human visual system’s mixed adaptation condition and produces results comparable to many existing algorithms.

Based on a full-wave formulation, a vector boundary element method (VBEM) is proposed to model the photonic crystal fibers (PCFs) (microstructured fibers). The accuracy and efficiency of the approach are confirmed by comparing the results calculated with those in previous literatures. With employing the VBEM, the guiding characteristics, including the effective indexes, vector mode patterns, and the polarization properties of the PCFs are investigated. There polarization characteristics of the PCFs with elliptical air holes (EPCFs) and the one ring air-hole EPCF embedded in the step-index core are studied and discussed. In addition, based on the VBEM formulations, a novel and efficient numerical approach to calculate the dispersion parameters of the PCFs is also proposed. The effect of the PCF geometrical structure on the group velocity dispersion property is reviewed, and then the one-ring defect and two-ring defect PCFs are studied and designed for the ultra-flattened dispersion applications. As an example, a four-ring (two-ring defect) PCF with flattened dispersion of ¡Ó0.25 ps/km/nm from 1.295£gm to 1.725£gm wavelength is numerically demonstrated.

Color plays a vitally important role in the world we live in. It surrounds us everywhere we go. Achromatic life, restricted to black, white and grey, is extremely dull. Color fascinates artists, for it adds enormously to aesthetic appreciation, directly invoking thoughts, emotions and feelings. Color fascinates scientists. For decades, scientists in color imaging, printing and digital photography have striven to satisfy increasing demands for accuracy in color reproduc- tion. Fluorescence is a very common phenomenon observed in many objects such as gems and corals, writing paper, clothes, and even laundry detergent. Traditional color imaging algo- rithms exclude fluorescence by assuming that all objects have only an ordinary reflective com- ponent. The first part of the thesis shows that the color appearance of an object with both reflective and fluorescent components can be represented as a linear combination of the two components. A linear model allows us to separate the two components using independent component analysis (ICA). We can then apply different algorithms to each component, and combine the results to form images with more accurate color. Displaying color images accurately is as important as reproducing color images accurately. The second part of the thesis presents a new, practical model for displaying color images on self-luminous displays such as LCD monitors. It shows that the model accounts for human visual system’s mixed adaptation condition and produces results comparable to many existing algorithms.