Neste trabalho abordamos o problema de coloraÃÃo de vÃrtices via programaÃÃo inteira. Uma versÃo expandida da formulaÃÃo por conjuntos independentes à utilizada para abrigar outras sub-estruturas do grafos alÃm dos vÃrtices. Cada uma dessas sub-estruturas define uma restriÃÃo que determina quantos conjuntos independentes sÃo necessarios para cobrir aquele subgrafo. Experimentos com um mÃtodo de geraÃÃo de cortes e colunas para o problema sÃo feitos para determinar um limite inferior para um conjunto de instÃncias classicas para esse problema a biblioteca DIMACS. / In this work the vertex coloring problem is approached via integer programming. A tighter version of the independent set formulation is used, where the vertex-related constraints are substituted by subgraph-related constraints. Each constraint establishes a lower bound on the number of independent sets intersecting a subgraph H. It is shown a sufficient condition for this inequality to define a facet of the associated polytope. Basically, H is required to be color critical, not included in another color critical subgraph, and to have a connected complement. Also, the column generation algorithm proposed by Mehotra and Trick (INFORMS Journal in Computing, 1996) is adapted to allow the addition of cutting planes and to provide lower bounds along the process, which may abbreviate its end. Some computational experiments are reported.

de Bruijn graphs are attractive due to its simplicity of routing messages between two nodes and the capability of fault tolerance. The shortest path from a node V to a node W in the directed binary de Bruijn graph can be obtained by firstly determining the longest substring, common to the right/left of V and to the left/right of W. Then L-operations/R-operations are performed to finish this routing process. However, this method does not always find the shortest path in the undirected binary de Bruijn graph. In this dissertation, we propose a shortest path routing algorithm which requires O(m2) time. We also design a fault-tolerant routing algorithm which provides the shortest path and another node-disjoint path of length at most m + log2m + 4. Our algorithm can tolerate one node failure in the m-dimensional binary de Bruijn network. In concurrent systems, a 1-fair alternator design is optimal if each processor can execute the critical step once in the fewest steps. This problem corresponds to use the minimum number of colors to color the processors in the system. Thus, the optimal design of a 1-fair alternator problem can be transformed into the coloring problem. We propose a simple and fast algorithm to solve the node coloring problem on the undirected binary de Bruijn graph. In our algorithm, the number of colors used is 3, and it is an optimal design. We also extend our method to solve the coloring problem on k-ary de Bruijn graphs. We first present a simple algorithm which needs 2k colors. By slight improvement, the number of required colors is reduced to k+1.

An alternator is a self-stabilizing system which consists of a network of concurrent processors. One of its properties is that any two processors of an alternator system cannot execute the critical step at the same time if they are adjacent. This exclusion property transforms the alternator design problem into the coloring problem. And an alternator is said to be 1-fair if no processor executes the critical step twice when one or more other processors have not executed the critical step yet. The simplicity of routing message and the capability of fault tolerance of de Bruijn networks attract us to design 1-fair alternator on them. In this thesis, two algorithms are proposed to solve the coloring problem on the de Bruijn network. The first one uses $2ceil{log_2k}+1$ colors to color the $k$-ary de Bruijn graph with two digits, while the second one uses $p+1$ only colors, where ${{p-1}choose{floor{(p-1)/2}}} < k leq {pchoose{floor{p/2}}}$. We also prove that the second coloring method is optimal when $k = {pchoose{floor{p/2}}}$. In other words, the chromatic number of the $k$-ary de Bruijn graph with two digits is $p+1$, where $k = {pchoose{floor{p/2}}}$. Furthermore, the extension of our coloring method can be applied to the $k$-ary de Bruijn graph with three or more digits.

No description available.

A mixed graph is a simple graph in which a subset of the edges have been assigned directions to form arcs. For non-negative integers j and k, a (j, k)−mixed graph is a mixed graph with j types of arcs and k types of edges. The collection of (j, k)−mixed graphs contains simple graphs ((0,1)−mixed graphs), oriented graphs ((1,0)-mixed graphs) and k−edge-coloured graphs ((0, k)−mixed graphs). A homomorphism is a vertex mapping from one (j,k)−mixed graph to another in which edge type is preserved, and arc type and direction are preserved. An m−colouring of a (j, k)−mixed graph is a homomorphism from that graph to a target with m vertices. The (j, k)−chromatic number of a (j, k)−mixed graph is the least m such that an m−colouring exists. When (j, k) = (0, 1), we see that these definitions are consistent with the usual definitions of graph homomorphism and graph colouring. Similarly, when (j, k) = (1, 0) and (j, k) = (0, k) these definitions are consistent with the usual definitions of homomorphism and colouring for oriented graphs and k−edge-coloured graphs, respectively. In this thesis we study the (j, k)−chromatic number and related parameters for different families of graphs, focussing particularly on the (1, 0)−chromatic number, more commonly called the oriented chromatic number, and the (0, k)−chromatic number. In examining oriented graphs, we provide improvements to the upper and lower bounds for the oriented chromatic number of the families of oriented graphs with maximum degree 3 and 4. We generalise the work of Sherk and MacGillivray on the 2−dipath chromatic number, to consider colourings in which vertices at the ends of iii a directed path of length at most k must receive different colours. We examine the implications of the work of Smolikova on simple colourings to study of the oriented chromatic number of the family of oriented planar graphs. In examining k−edge-coloured graphs we provide improvements to the upper and lower bounds for the family of 2−edge-coloured graphs with maximum degree 3. In doing so, we define the alternating 2−path chromatic number of k−edge-coloured graphs, a parameter similar in spirit to the 2−dipath chromatic number for oriented graphs. We also consider a notion of simple colouring for k−edge-coloured graphs, and show that the methods employed by Smolikova ́ for simple colourings of oriented graphs may be adapted to k−edge-coloured graphs. In addition to considering vertex colourings, we also consider incidence colourings of both graphs and digraphs. Using systems of distinct representatives, we provide a new characterisation of the incidence chromatic number. We define the oriented incidence chromatic number and find, by way of digraph homomorphism, a connection between the oriented incidence chromatic number and the chromatic number of the underlying graph. This connection motivates our study of the oriented incidence chromatic number of symmetric complete digraphs. / Graduate

The performance of eleven 'Valencia Late' and nine 'Washington Navel' orange (Citrus sinensis) clones all on rough lemon (Citrus jambhiri) rootstock was evaluated. Significant differences in trunk cross sectional area, plant canopy volume, cumulative yield and yield efficiency were found between clones of different citrus cultivars. Some clones such as VL106, VL139, VL185 and WN204 appeared to be promising in terms of good growth characteristics and high yield, and could therefore be used for the national performance trials. Studies on post-harvest degreening of 'Valencia Late' oranges were also carried out at Matuga Regional Research Sub-Centre (Kenya) in a series of experiments. Fully mature fruits were dipped for three minutes in 0, 500, 1000, 1500, 2000, 2500 and 3000 ppm concentrations of ethephon. Fruits wrapped in aluminum foil shrivelled less and retained their firmness and freshness. Rind brightness increased by dipping of fruits in ethephon (2000) ppm giving a good colour change. Dipping fruits a second time three days after the first dip did not have any significant effect on colour change. (Chemical names used: (2-Chloroethyl)phosphonic acid (ethephon).

There has been extensive research activities in the last couple of years to efficiently determine large sparse Jacobian matrices. It is now well known that the estimation of Jacobian matrices can be posed as a graph coloring problem. Unidirectional coloring by Coleman and More [9] and bidirectional coloring independently proposed by Hossain and Steihaug [23] and Coleman and Verma [12] are techniques that employ graph theoretic ideas. In this thesis we present heuristic and exact bidirectional coloring techniques. For bidirectional heuristic techniques we have implemented variants of largest first ordering, smallest last ordering, and incidence degree ordering schemes followed by the sequential algorithm to determine the Jacobian matrices. A "good" lower bound given by the maximum number of nonzero entries in any row of the Jacobian matrix is readily obtained in an unidirectional determination. However, in a bidirectional determination no such "good" lower bound is known. A significant goal of this thesis is to ascertain the effectiveness of the existing heuristic techniques in terms of the number of matrix-vector products required to determine the Jacobian matrix. For exact bidirectional techniques we have proposed an integer linear program to solve the bidirectional coloring problem. Part of exact bidirectional coloring results were presented at the "Second International Workshop on Cominatorial Scientific Computing (CSC05), Toulouse, France." / viii, 83 leaves ; 29 cm.

Reed's conjecture is a proposed upper bound for the chromatic number of a graph. Reed's conjecture has already been proven for several families of graphs. In this paper, I show how one of those families of graphs can be extended to include additional graphs and also show that Reed's conjecture holds for a family of graphs known as cycle-power graphs, and also for their complements.

Red radish anthocyanin extract (RAE) was investigated for coloring brined cherries as an alternative to FD&C Red No. 40. Red radish (Raphanus sativus L.) anthocyanins were extracted from liquid nitrogen powdered epidermal tissue using acetone, partitioned with chloroform, and isolated using C-18 resin. The monomeric anthocyanin content was determined by pH differential to be 154 ± 13 mg/100 g of epidermal tissue (on pelargonidin-glucoside basis). The major pigments were identified as pelargonidin-3-sophoroside-5-glucoside monoacylated with p-coumaric or ferulic acids by HPLC and spectral analyses. Primary and secondary bleached cherries were sweetened to 40° Brix (pH of 3.50), and colored using two concentrations of RAE (600 and 1200 mg/L syrup, designated Cl and C2) and FD&C Red No. 40 (200 ppm). Color was measured for both cherries and syrup. Reflectance measurements (CIE L*, a*, b*), chroma and hue angle, showed that RAE imparted red color to the cherries and syrup extremely close to that of FD&C Red No. 40. RAE C2 gave the primary bleached cherries the closest color characteristics (L*= 18.20, a*= 20.00, b*= 8.47) to FD&C Red No. 40 (L*= 18.00, a*= 24.35, b*= 12.13). RAE Cl gave the secondary bleached cherries the closest color characteristics (L*= 15.27, a*= 16.21, b*= 5.21) to FD&C Red No. 40 (L*= 16.38, a*= 19.91, b*= 8.99). Color and pigment stability of secondary bleached cherries were evaluated during a year of storage in the dark at 25°C. Monomeric anthocyanin degradation followed first-order kinetics and the half-lives were 29 and 33 weeks for syrups colored with RAE Cl and RAE C2, respectively. However, cherry color showed no significant changes in hue, color intensity nor lightness during storage. Color changes of syrup samples over time were dependant on anthocyanin concentration, higher anthocyanin concentration exerted a protective effect on color stability. Haze formation was observed in syrup samples colored with RAE, possibly due to pigment polymerization. Syrup samples colored with RAE and FD&C Red No. 40 were also exposed to light for a year at 25°C. Light had a small but significant effect on L*, a*, and monomeric anthocyanin content. From color and pigment stability data and visual observations we concluded that RAE was effective in coloring secondary bleached cherries with results very similar to those of FD&C Red No. 40 for 6 months of storage. / Graduation date: 1995

Graduation date: 1940