Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work brings an approach to the basic notions of Graph Theory, presenting historical context, concepts, de nitions and examples in order to provide the reader with previous knowledge of the theory. The main objective is to perform a study of the graphs applied to the staining using the dual graph and the method of the greedy algorithm. To do so, we will present the demonstration attempt of the 4-Color Theorem that had been developed by Kempe and the proof of the 5-Color Theorem, made 11 years later by Heawood. Finally, we will seek the resolution of some situations problems that will be modeled through the coloring of vertices. / Este trabalho traz uma abordagem às noções da Teoria dos Grafos, apresentando contexto histórico, conceitos, definições e exemplos com o intuito de proporcionar ao leitor conhecimentos prévios da teoria. O principal objetivo é efetuar um estudo dos grafos aplicados à coloração mediante o uso do grafo dual e o métdo do algoritmo guloso. Para tanto, executaremos um esboço acerca da tentativa de demonstração do Teorema das 4 Cores que fora desenvolvida por Kempe e da prova do Teorema das 5 Cores, feita 11 anos mais tarde por Heawood. Por fim, buscaremos a resolução de algumas situações problemas que serão modeladas através da coloração de vértices. / São Cristóvão, SE

Orientador: Celia Picinin de Mello / Tese (doutorado) - Universidade Estadual de Campinas , Instituto de Computação / Made available in DSpace on 2018-08-06T12:11:33Z (GMT). No. of bitstreams: 1 Campos_ChristianeNeme_D.pdf: 1048367 bytes, checksum: e8270db6704873ddaf2043927ca93e99 (MD5) Previous issue date: 2006 / Doutorado / Teoria dos Grafos / Doutor em Ciência da Computação

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-09-21T18:30:26Z No. of bitstreams: 1 lilianerodriguesdealmeida.pdf: 4991501 bytes, checksum: 0d4dbf0a69e24ecbaec4ff6581381709 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-09-22T15:22:19Z (GMT) No. of bitstreams: 1 lilianerodriguesdealmeida.pdf: 4991501 bytes, checksum: 0d4dbf0a69e24ecbaec4ff6581381709 (MD5) / Made available in DSpace on 2017-09-22T15:22:19Z (GMT). No. of bitstreams: 1 lilianerodriguesdealmeida.pdf: 4991501 bytes, checksum: 0d4dbf0a69e24ecbaec4ff6581381709 (MD5) Previous issue date: 2017-02-23 / FAPEMIG - Fundação de Amparo à Pesquisa do Estado de Minas Gerais / Este trabalho propõe um método de reposicionamento de polilinhas em 2D que representam curvas cilíndricas para manter a distância entre os segmentos de reta com pelo menos e unidades mais os raios de dois cilindros quaisquer, cada um associado a uma polilinha. A abordagem depende da construção de um grafo que representa os pontos que violam uma distância mínima, reduzindo o problema de remoção de contatos ao problema de coloração de grafos. Uma vez construído, o grafo é colorido usando uma heurística para encontrar quais vértices podem estar no mesmo plano. O número final de cores indica o número de planos na terceira dimensão necessários para resolver os contatos. Propõe-se também duas abordagens para calcular os deslocamentos dos vértices a partir dos grafo e das cores computadas, ambas projetadas para obter florestas com a soma de deslocamentos mínima. Os resultados mostram a eficiência da construção do grafo, da coloração do grafo e do mapeamento de cor em planos. Aplica-se o método proposto e as duas abordagens de deslocamento no problema de desentrelaçamento de florestas de polilinhas que representam nanotubos de carbono. O número de contatos cai significativamente depois da aplicação do método mesmo em florestas de tubos densas e com vários contatos. / This work proposes a method to reposition of 2D polylines representing cylindrical curves in order to keep the distance between line segments with at least c unities plus the radii of any two cylinders, each associated with a polyline. Our approach relies on the construction of a graph representing the points violating a minimum distance, reducing the contact removal problem to a graph coloring problem. Once constructed, the graph is colored using a heuristic to find out which vertices can be in the same plane. The final number of colors indicates the number of planes in third dimension needed to solve contacts. We also propose two approaches to compute vertex displacements from the computed graph and colors, both designed to obtain forests with minimum sum of displacements. Results show the efficiency of the graph construction, graph coloring and color to plane mappings. We apply the proposed method and the two displacement approaches on the problem of untangling forests of polylines representing carbon nanotubes. The number of contacts drops significantly after applying our method even in dense forests of tubes with numerous contacts.

For a finite relational structure A, the Constraint Satisfaction Problem with template A, or CSP(A), is the problem of deciding whether an input relational structure X admits a homomorphism to A. The CSP dichotomy conjecture of Feder and Vardi states that for any A, CSP(A) is either in P or NP-complete. In the first part we present the algebraic approach to CSP and summarize known results about CSP for digraphs, also known as the H-coloring problem. In the second part we study a class of oriented trees called special polyads. Using the algebraic approach we confirm the dichotomy conjecture for special polyads. We provide a finer description of the tractable cases and give a construction of a special polyad T such that CSP(T) is tractable, but T does not have width 1 and admits no near-unanimity polymorphisms.

Dans cette thèse, nous nous intéressons à la coloration circulaire des graphes planaires. Des bornes supérieures ont été données pour des graphes avec degré maximum borné, avec girth, la longueur de son plus petit cycle, bornée, avec des cycles manquants, etc. Ici nous donnerons de nouvelles bornes pour les graphes avec degré moyen maximum borné. Nous étudions également la coloration totale et la coloration (d,1)-totale de plusieurs familles infinies de graphes. Nous décrivons le nouveau concept de coloration (d,1)-totale circulaire. Enfin, nous discutons les conditions nécessaires pour qu'un graphe planaire admette une coloration acyclique par listes de taille 4. / In this thesis, we study the circular coloring of planar graphs. Upper bounds have been given for graphs with bounded maximum degree, with bounded girth, that is the length of its smallest cycle, with missing cycles, and so on. It has also been studied for graphs with bounded maximum average degree. Here we give new upper bounds for that latter case. We also study the total coloring and ($d,1$)-total labeling of a few infinite families of graphs and describe the new concept of circular ($d,1$)-total labeling of graphs. In the last part, we will discuss conditions for a planar graph to be acyclically $4$-choosable.

Orientadores: Nelma de Mello Silva Oliveira, Gisela de Aragão Umbuzeiro, Simone Valente Campos / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-27T02:06:39Z (GMT). No. of bitstreams: 1 Resende_MariellyReis_M.pdf: 1924615 bytes, checksum: 1591718b0b86c23e64a29629b4589246 (MD5) Previous issue date: 2015 / Resumo: Embora tenha grande utilidade e diversas aplicações nos setores industriais, há anos a discussão sobre o potencial genotóxico do corante tartrazina vem sendo abordada, uma vez que há vários resultados controversos descritos na literatura. É provável que a presença de impurezas nas amostras possa ser uma das causas do possível potencial mutagênico. Dessa forma, esse estudo visa avaliar a atividade mutagênica do corante tartrazina com diferentes graus de pureza e possíveis interferentes presentes nas amostras, utilizando o ensaio Salmonella/microssoma a partir das linhagens recomendadas pela OECD 471. Os resultados obtidos demonstraram que o corante tartrazina ?99 % e o corante tartrazina comercial 90%, não apresentaram atividade mutagênica para as linhagens TA97a, TA98, TA100, TA1535 e TA102 demonstrando ausência de impurezas mutagênicas ou que as mesmas estejam em baixas concentrações nas amostras avaliadas / Abstract: Although very useful and diverse applications in industry, for years the discussion on the genotoxic potential of the dye tartrazine has been addressed, since there are several controversial results in the literature. It is likely that the presence of impurities in the samples may be a cause of the possible mutagenic potential. Thus, this study aims to evaluate the mutagenic activity of the dye tartrazine with different degrees of purity and possible interferences present in the samples, using the Salmonella / microsome test from the lines recommended by the OECD 471. The results showed that the dye tartrazine ?99 % and the dye tartrazine commercial 90% showed no mutagenic activity for the strains TA97, TA98, TA100, TA1535 and TA102 showing absence of mutagenic impurities or that they are in low concentrations in the analyzed samples / Mestrado / Tecnologia e Inovação / Mestra em Tecnologia

In this thesis, we deal with rainbow colorings of graphs. We engage not with the rainbow connection number but with counting of rainbow colorings in graphs with k colors. We introduce the rainbow polynomial and prove some results for some special graph classes. Furthermore, we obtain bounds for the rainbow polynomial. In addition, we define some edge colorings related to the rainbow coloring, like the s-rainbow coloring and the 2-rainbow coloring. For this edge colorings, polynomials are defined and we prove some basic properties for this polynomials and present some formulas for the calculation in special graph classes. In addition, we consider in this thesis counting problems related to the rainbow coloring like rainbow pairs and rainbow dependent sets. We introduce polynomials for this counting problems and present some general properties and formulas for special graph classes.

This thesis consists of three parts devoted to graph labeling, hereditary graph classes, and parameterized complexity. Packing coloring, originally Broadcasting Chromatic number, assigns natural numbers to vertices such that vertices with the same label are in distance at least the value of the label. This problem is motivated by the assignment of frequencies to the transmitters. We improve hardness on chordal graphs. We proof that packing coloring on chordal graphs with diameter 3 is very hard to approximate. Moreover, we discuss several positive results on interval graphs and on related structural graph parameters. Hereditary graph classes are preserved under vertex deletion. We study graphs that do not contain an induced subgraph H. We prove that 3-coloring is polynomial-time solvable for (P3 + P4)-free and (P2 + P5)-free graphs and thus we have solved the last open cases for the problem on H-free graphs where H has up to 7 vertices. Fair problems are a modification of graph deletion problems, where, instead of minimizing the size of the solution, the aim is to minimize the maximum number of neighbors in the deleted set. We show that those problems can be solved in FPT time for an MSO1 formula parameterized by the size of the formula and the twin cover of the graph. Moreover, we define a basic...

Orientador: Alvaro de Baptista Neto / Banca: Alberto Colli Badino Junior / Banca: Fernando Lucas Primo / Resumo: Com o desenvolvimento da indústria moderna, houve o aumento na utilização de colorantes artificiais em diferentes áreas, entre elas destaca-se o setor alimentício e farmacêutico. Com a utilização contínua desses colorantes no ramo alimentício foi verificado, dependendo da classe e da concentração, o grande potencial desses compostos causarem diversas doenças, dentre elas o câncer. Com isso, é possível observar um crescente desenvolvimento de tecnologias que visam à obtenção de processos de produção de colorantes naturais, de origem biológica, que são considerados mais saudáveis e menos nocivos à saúde humana. Nesse contexto, as antraquinonas, se destacam por possuírem compostos que podem ser utilizados como colorante natural. Há muitos trabalhos na literatura destacando diversas ações desses compostos naturais, como por exemplo, atividade hepatoprotetora, anticancerígena, antimicrobiana, antifúngica, antiviral, antidiabética, antioxidante, entre outras. Nesse sentido, visto a grande importância de colorantes naturais pertencentes ao grupo das antraquinonas, o presente trabalho teve como objetivo desenvolver métodos para extração e quantificação de um colorante natural pertencente à classe das antraquinonas, e os resultados foram satisfatórios. Foi possível determinar o processo de purificação e extração através de cromatografia de adsorção, utilizando como adsorvente a resina IRA-410 e como eluente solução de Cloreto de Sódio 5,0% e Etanol PA, onde foi possível obter uma recu... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: With modern industry development, the use of artificial colors in different areas has increased, among them, the alimentary segment. With the continuous use of these dyes in the food industry, it was verified that depending on the class and concentration, there's a huge potential of these compounds cause various diseases, among them cancer. With this, it is possible to observe a growing development of technologies that aim at obtaining biological origin natural dyes production processes, that are considered healthier and less harmful to human health. In this context, the anthraquinones, stand out because they have compounds that can be used as a natural dye. There are many works in the literature highlighting several actions of these natural compounds, such as hepatoprotective, anticancer, antimicrobial, antifungal, antiviral, antidiabetic, antioxidant, among others activities. In this sense, given the great importance of natural dyes belonging to the quinones group, the present work aimed to develop methods for extracting and quantifying a natural dye belonging to the class of anthraquinones, and the results were satisfactory. It was possible to determine the purification and extraction process by adsorption chromatography using as adsorbent IRA-410 resin and as eluent 5.0% Sodium Chloride solution and Ethanol PA, where it was possible to obtain a recovery of 100% and a yield of 86% when the fixed bed tests were performed, obtaining a promising method for determining the con... (Complete abstract click electronic access below) / Mestre

Every graph G contains a minimum vertex-coloring with the property that at least one color class of the coloring is a maximal independent set (equivalently, a dominating set) in G. Among all such minimum vertex-colorings of the vertices of G, a coloring with the maximum number of color classes that are dominating sets in G is called a dominating-χ-coloring of G. The number of color classes that are dominating sets in a dominating-χ-coloring of G is defined to be the dominating-χ-color number of G. In this paper, we continue to investigate the dominating-χ-color number of a graph first defined and studied in [1].