RODRIGUES, Carlos Diego. Limites inferiores para o problema de coloração de vértices via geração de cortes e colunas. 2008. 79 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2008. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T11:50:40Z No. of bitstreams: 1 2005_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-14T15:28:23Z (GMT) No. of bitstreams: 1 2005_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) / Made available in DSpace on 2016-07-14T15:28:23Z (GMT). No. of bitstreams: 1 2005_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) Previous issue date: 2008 / 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. / 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.

O Rio Grande do Sul é um dos principais produtores de geodos de ágatas do mundo. Na região do Salto do Jacuí existe um tipo de ágata cinza, ideal para tingimento, chamada “Umbu”. Essas ágatas porosas permitem a introdução de alguns corantes em sua estrutura, tornando-as coloridas artificialmente. Este trabalho teve como objetivo avaliar a colorimetria como ferramenta para o controle das cores no tingimento de ágatas. Avaliou-se a resistência da cor em função do tempo e locais de exposição para ágatas tingidas com corantes orgânicos e inorgânicos. Estudaram-se as ágatas coloridas com os seguintes corantes orgânicos: verde brilhante (verde), rodamina B (rosa), cristal violeta (roxo) e vermelho sangue (vermelho). Também se avaliaram as colorações dos seguintes procedimentos clássicos de tingimento: ferrocianeto de potássio/sulfato de ferro (azul), nitrato de ferro/calcinação (vermelho), ácido crômico/carbonato de amônio (verde) e açúcar/ácido sulfúrico (preto). O procedimento experimental consistiu em expor chapas de ágatas em três ambientes com luminosidade distintas (escuro, doméstico e ao ar livre), por um período de 30 semanas, sendo a variação da cor analisada, com um espectrofotômetro Minolta 2600 d, utilizando o sistema colorimétrico L* a* b* aliada à colorimetria diferencial.Os resultados demonstraram que a colorimetria diferencial se mostrou uma ferramenta eficiente para avaliar a perda de cor em ágatas coloridas artificialmente. Os métodos clássicos de tingimento em verde e vermelho produzem cores estáveis. Já os procedimentos clássicos para coloração azul e preto apresentam variações, podendo ser considerados fotossensíveis. Todos os corantes orgânicos estudados (anilinas) sofrem degradação pela luz. / The State of Rio Grande do Sul in Brazil, is one of the main world producers of geodes of agates: (a stone having a cavity lined with crystals). The gray type of agates, found in the region of Salto do Jacuí, called: “UMBÚ”, is ideal for coloring. These porous agates are suitable to some artificial colorings applications on their walls. The purpose of this paper is to analyze the measurements of agates colored by means of a colorimeter. The aging factor of colored agates with organic and inorganic dyes was evaluated. The colored agates with following organic colorings were analyzed: Brilliant green, rhodamine B (pink), crystal violet (purple), and blood red. The coloring of the following standard procedures of dyeing were also evaluated: Ferrocyanid of potassium/sulfate of iron (blue), nitrate of iron/calcinations (red), chromic acid/carbonate of ammonium (green), and sugar/sulfuric acid (black). The experimental procedures consisted of exposing agate plates in three places with distinct luminosity (dark, in door/domestic, and outdoors). The color variation was analyzed with a Minolta 2600d spectrophotometer, using the L* a* b* colorimetrical system as related to the colorimetric differential.The results have demonstrated that the colorimetric differential revealed itself as an efficient tool to evaluate the loss of artificially colored agates. The standards procedures for dyeing in green and red produce stable colors. The standard procedures, for dyeing in blue and black, offer variations, as they can be considered photosensitive. All the studied organic colorings (anilines) are degraded by the light.

O Rio Grande do Sul é um dos principais produtores de geodos de ágatas do mundo. Na região do Salto do Jacuí existe um tipo de ágata cinza, ideal para tingimento, chamada “Umbu”. Essas ágatas porosas permitem a introdução de alguns corantes em sua estrutura, tornando-as coloridas artificialmente. Este trabalho teve como objetivo avaliar a colorimetria como ferramenta para o controle das cores no tingimento de ágatas. Avaliou-se a resistência da cor em função do tempo e locais de exposição para ágatas tingidas com corantes orgânicos e inorgânicos. Estudaram-se as ágatas coloridas com os seguintes corantes orgânicos: verde brilhante (verde), rodamina B (rosa), cristal violeta (roxo) e vermelho sangue (vermelho). Também se avaliaram as colorações dos seguintes procedimentos clássicos de tingimento: ferrocianeto de potássio/sulfato de ferro (azul), nitrato de ferro/calcinação (vermelho), ácido crômico/carbonato de amônio (verde) e açúcar/ácido sulfúrico (preto). O procedimento experimental consistiu em expor chapas de ágatas em três ambientes com luminosidade distintas (escuro, doméstico e ao ar livre), por um período de 30 semanas, sendo a variação da cor analisada, com um espectrofotômetro Minolta 2600 d, utilizando o sistema colorimétrico L* a* b* aliada à colorimetria diferencial.Os resultados demonstraram que a colorimetria diferencial se mostrou uma ferramenta eficiente para avaliar a perda de cor em ágatas coloridas artificialmente. Os métodos clássicos de tingimento em verde e vermelho produzem cores estáveis. Já os procedimentos clássicos para coloração azul e preto apresentam variações, podendo ser considerados fotossensíveis. Todos os corantes orgânicos estudados (anilinas) sofrem degradação pela luz. / The State of Rio Grande do Sul in Brazil, is one of the main world producers of geodes of agates: (a stone having a cavity lined with crystals). The gray type of agates, found in the region of Salto do Jacuí, called: “UMBÚ”, is ideal for coloring. These porous agates are suitable to some artificial colorings applications on their walls. The purpose of this paper is to analyze the measurements of agates colored by means of a colorimeter. The aging factor of colored agates with organic and inorganic dyes was evaluated. The colored agates with following organic colorings were analyzed: Brilliant green, rhodamine B (pink), crystal violet (purple), and blood red. The coloring of the following standard procedures of dyeing were also evaluated: Ferrocyanid of potassium/sulfate of iron (blue), nitrate of iron/calcinations (red), chromic acid/carbonate of ammonium (green), and sugar/sulfuric acid (black). The experimental procedures consisted of exposing agate plates in three places with distinct luminosity (dark, in door/domestic, and outdoors). The color variation was analyzed with a Minolta 2600d spectrophotometer, using the L* a* b* colorimetrical system as related to the colorimetric differential.The results have demonstrated that the colorimetric differential revealed itself as an efficient tool to evaluate the loss of artificially colored agates. The standards procedures for dyeing in green and red produce stable colors. The standard procedures, for dyeing in blue and black, offer variations, as they can be considered photosensitive. All the studied organic colorings (anilines) are degraded by the light.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Estudou-se o processo de adsorção dos seguintes corantes: Laranja Indosol, Rhodamina B, Vermelho Congo e Azul Indosol sobre a argila montmorilonita em meio aquoso nas temperaturas de 288, 298, 308 e 318K. Os melhores rendimentos foram obtidos para temperatura de 288 e 298K. O processo de remoção desses corantes foi estudado a partir dos dados de equilíbrio e cinética para cada temperatura. O modelo de Freundlich foi o que melhor representou os dados experimentais de isotermas de adsorção para os corantes em todas as temperaturas consideradas. O modelo cinético de pseudo-segunda ordem foi o que melhor ajustou os dados experimentais das interações envolvidas no processo. Verificou-se que tratar de um processo endotérmico, e as interações corante/MTT aumentam o grau de espontaneidade das reações com a elevação da temperatura do processo. Para os difratogramas obtidos para as amostras de LI/MTT, VC/MTT e AI/MTT foi possível verificar que todos os ângulos de incidência mostram que não há grandes mudanças essencialmente na sobreposição principalmente no ângulo de incidência (2θ) quando comparadas a MTT. A análise termogravimétrica mostra que, a decomposição térmica da MTT completa começou acerca de 30C e foi completamente até 1000C e sendo identificadas quatro perdas de peso distintas. A intensidade das bandas de absorção presentes nos espectros na região do infravermelho foi reduzida após a adsorção dos corantes denotando ainda que o processo de adsorção dos corantes não modifica a estrutura da montmorilonita. / Studied the adsorption of the following dye: Orange Indosol, Rhodamine B, Congo Red and Blue Indosol about montmorillonite clay in an aqueous medium at temperatures of 288, 298, 308 and 318K. The best yields were obtained at temperatures of 288 and 298K. The process of removing these dyes was studied from kinetic and equilibrium data for each temperature. The Freundlich model was best represented the experimental data of adsorption isotherms for dyes at all temperatures considered. The kinetic model of pseudo-second order was the best fit to the experimental data of the interactions involved in the process. It was found that treating an endothermic process and the interactions dye / MTT increase the degree of spontaneity of reactions with increasing process temperature. For the XRD patterns obtained for samples of LI / MTT, VC / MTT and AI / MTT was possible to verify that all incident angles show no major changes in essentially overlap mainly in the incidence angle (2θ) when compared to MTT. Thermogravimetric analysis shows that the thermal decomposition of the complete MTT began about 30 C and was completely up to 1000 C and four different weight losses are identified. The intensity of the absorption bands present in the spectrum in the infrared region was reduced after adsorption of the dyes also showing that the adsorption of the dye does not alter the structure of montmorillonite.

A graph is (2, 1)-colorable if it allows a partition of its vertices into two classes such that both induce graphs with maximum degree at most one. A non-(2, 1)-colorable graph is minimal if all proper subgraphs are (2, 1)-colorable. We prove that such graphs are 2-edge-connected and that every edge sits in an odd cycle. Furthermore, we show properties of edge cuts and particular graphs which are no induced subgraphs. We demonstrate that there are infinitely many minimal non-(2, 1)-colorable graphs, at least one of order n for all n ≥ 5. Moreover, we present all minimal non-(2, 1)- colorable graphs of order at most seven. We consider the maximum degree of minimal non-(2, 1)-colorable graphs and show that it is at least four but can be arbitrarily large. We prove that the average degree is greater than 8/3 and give sufficient properties for graphs with average degree greater than 14/5. We conjecture that all minimal non-(2, 1)-colorable graphs fulfill these properties.

M.Sc. / Within the field of Graph Theory the many ways in which graphs can be coloured have received a lot of attention over the years. T.R. Jensen and B. Toft provided a summary in [8] of the most important results and research done in this field. These results were cited by R. Diestel in [5] as “The Four Colour Problem” wherein it is attempted to colour every map with four colours in such a way that adjacent countries will be assigned different colours. This was first noted as a problem by Francis Guthrie in 1852 and later, in 1878, by Cayley who presented it to the London Mathematical Society. In 1879 Kempe published a proof, but it was incorrect and lead to the adjustment by Heawood in 1890 to prove the five colour theorem. In 1977 Appel and Haken were the first to publish a solution for the four colour problem in [2] of which the proof was mostly based on work done by Birkhoff and Heesch. The proof is done in two steps that can be described as follows: firstly it is shown that every triangulation contains at least one of 1482 certain “unavoidable configurations” and secondly, by using a computer, it is shown that each of these configurations is “reducible”. In this context the term “reducible” is used in the sense that any plane triangulation containing such a configuration is 4-colourable by piecing together 4- colourings of smaller plane triangulations. These two steps resulted in an inductive proof that all plane triangulations and therefore all planar graphs are 4-colourable.

abstract: The chromatic number $\chi(G)$ of a graph $G=(V,E)$ is the minimum number of colors needed to color $V(G)$ such that no adjacent vertices receive the same color. The coloring number $\col(G)$ of a graph $G$ is the minimum number $k$ such that there exists a linear ordering of $V(G)$ for which each vertex has at most $k-1$ backward neighbors. It is well known that the coloring number is an upper bound for the chromatic number. The weak $r$-coloring number $\wcol_{r}(G)$ is a generalization of the coloring number, and it was first introduced by Kierstead and Yang \cite{77}. The weak $r$-coloring number $\wcol_{r}(G)$ is the minimum integer $k$ such that for some linear ordering $L$ of $V(G)$ each vertex $v$ can reach at most $k-1$ other smaller vertices $u$ (with respect to $L$) with a path of length at most $r$ and $u$ is the smallest vertex in the path. This dissertation proves that $\wcol_{2}(G)\le23$ for every planar graph $G$. The exact distance-$3$ graph $G^{[\natural3]}$ of a graph $G=(V,E)$ is a graph with $V$ as its set of vertices, and $xy\in E(G^{[\natural3]})$ if and only if the distance between $x$ and $y$ in $G$ is $3$. This dissertation improves the best known upper bound of the chromatic number of the exact distance-$3$ graphs $G^{[\natural3]}$ of planar graphs $G$, which is $105$, to $95$. It also improves the best known lower bound, which is $7$, to $9$. A class of graphs is nowhere dense if for every $r\ge 1$ there exists $t\ge 1$ such that no graph in the class contains a topological minor of the complete graph $K_t$ where every edge is subdivided at most $r$ times. This dissertation gives a new characterization of nowhere dense classes using generalized notions of the domination number. / Dissertation/Thesis / Doctoral Dissertation Mathematics 2020

Let G and H be graphs. We say G is H-critical, if every proper subgraph of G except G itself is homomorphic to H. This generalizes the widely known concept of k-color-critical graphs, as they are the case H = Kk - 1. In 1963 [T. Gallai, Kritiche Graphen, I., Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963), 373-395], Gallai proved that the vertices of degree k in a Kk-critical graph induce a subgraph whose blocks are either odd cycles or complete graphs. We generalize Gallai's Theorem for every H-critical graph, where H = Kk - 2 + H′, (the join of a complete graph Kk - 2 with any graph H′). This answers one of the two unknown cases of a problem given in [J. Nešetřil, Y. Nigussie, Finite dualities and map-critical graphs on a fixed surface. (Submitted to Journal of Combin. Theory, Series B)]. We also propose an open question, which may be a characterization of all graphs for which Gallai's Theorem holds.

The coloring matter in flowers has been used for centuries as a dye. Early man did not know the chemical nature of these coloring matters. Recent investigations have shown that the dark pigments whereas the lighter pigments of flowers are in the anthoxanthin group of pigments. Both of these groups of pigments have a heterocyclic structure. A large number of these pigments have been isolated and identified. The object of this research was to isolate and identity the coloring matter in the Camillia japonica (Belgian red) flowers. This was done by extracting the pigment with methanol and then crystallizing the pigment as a chloride. Color reactions, solubility, spectra, and other physical properties were obtained for this pigment.

No description available.