Os problemas de colorac Ëao de vÂertices e de arestas, que consistem em determinar o menor nÂumero de cores necessÂarias para colorir os vÂertices e arestas de um grafo, respectivamente, de forma que vÂertices adjacentes e arestas adjacentes, respectivamente, possuem cores distintas, sËao problemas computacionalmente difÂıceis e sËao objeto de pesquisa recorrente em teoria do grafos em virtude de inÂumeros problemas prÂaticos que eles modelam. No presente trabalho, estudamos o pior desempenho dos algoritmos gulosos de colorac Ëao de vÂertices e de arestas. O algoritmo guloso tem o seguinte princÂıpio geral: receber, um a um, os vÂertices (respect. as arestas) do grafo a ser colorido, atribuindo sempre a menor cor possÂıvel ao vÂertice (resp. aresta) a ser colorido. Observamos que colorir de forma gulosa as arestas de um grafo equivale a colorir de forma gulosa o seu grafo linha, tendo sido este o maior interesse na pesquisa em colorac Ëao gulosa de arestas. O pior desempenho dos algoritmos Âe medido pelo maior nÂumero de cores que eles podem utilizar. No caso da colorac Ëao gulosa de vÂertices, esse Âe o nÂumero de Grundy ou nÂumero cromÂatico guloso do grafo. No caso da colorac Ëao de arestas, esse Âe o Âındice cromÂatico guloso ou Âındice de Grundy do grafo. Sabe-se que determinar o nÂumero de Grundy de um grafo qualquer Âe NP-difÂıcil. A complexidade de determinar o Âındice de Grundy de um grafo qualquer era entretanto um problema em aberto. Na presente dissertac Ëao, provamos dois resultados de complexidade. Provamos que o nÂumero de Grundy de um grafo (q,q−4) pode ser determinado em tempo polinomial. Essa classe contÂem estritamente a classe dos cografos e P4-esparsos para os quais o mesmo resultado havia sido estabelecido. Esse resultado generaliza portanto aqueles resultados. O algoritmo apresentado usa a decomposicÂËao primeval desses grafos, determinando o parËametro em tempo linear. No que se refere `a colorac Ëao de arestas, provamos que o problema de determinar o Âındice de Grundy Âe NP-completo para grafos em geral e polinomial para grafos caterpillar, implicando que o nÂumero de Grundy Âe polinomial para os grafos linha desses. Mais especificamente provamos que o Âındice de Grundy dos caterpillar Âe D ou D+1 e apresentamos um algoritmo polinomial para determinÂa-lo exatamente. / The vertices and edges colorings problems, which consists in determine the smallest number of colors needed to color the vertices and edges of a graph, respectively, so that adjacent vertices and adjacent edges, respectively, have distinct colors, are computationally hard problems and recurring subject of research in graph theory due to numerous practical problems they model. In this work, we study the worst performance of greedy algorithms for coloring vertices and edges. The greedy algorithm has the following general principle: to receive, one by one, the vertices (respect. edges) of the graph to be colored by assigning always the smallest possible color to the vertex (resp. edge) to be colored. We note that so greedy coloring the edges of a graph is equivalent to greedily coloring its line graph, this being the greatest interest in research on greedy edges coloring. The worst performance of the Algorithms is measured by the greatest number of colors they can use. In the case of greedy vertex coloring, this is the number of Grundy or greedy chromatic number of the graph. For the edge coloring, this is the greedy chromatic index or Grundy index of the graph. It is known that determining the Grundy number of any graph is NP-hard. The complexity of determining the Grundy index of any graph was however an open problem. In this dissertation, we prove two complexity results. We prove that the Grundy number of a (q,q−4)-graph can be determined in polynomial time. This class contains strictly the class of cografos P4-sparse for which the same result had been established. This result generalizes so those results. The presented algorithm uses the primeval decomposition of graphs, determining the parameter in linear time. About greedy edge coloring, we prove that the problem of determining the Grundy index is NP-complete for general graphs and polynomial for catepillar graphs, implying that the Grundy number is polynomial for graphs of line of caterpillars. More specifically, we prove that the Grundy index of a caterpillar is D or D+1 and present a polynomial algorithm to determine it exactly.

This dissertation is an inquiry into the origin, history, and interpretation of Genesis 4:26b, translatable as “then calling on the name of YHWH was begun”. Several methods, including philological analysis, semantic analysis, text criticism, and redaction criticism are brought to bear to understand the possible denotations of this verse and which are most likely given the context, what challenges exist to any preferable readings, and how those challenges might be addressed. Then, a survey is presented considering how ancient and modern interpreters have understood this half-verse, especially when considered in light of other passages that appear to contradict it. Potential interpretations are then laid out and assessed for plausibility before the historical and archaeological records are considered for what they suggest Gen 4:26b was actually read as meaning or altered contextually to mean at different points in Israelite history. Finally, a “speculative biography” of Gen 4:26b is provided, beginning with the origin of the ideas it presents in Israelite cultural memory and folklore, then laying out a model for how it was composed, understood, and recontextualized over time. It is tentatively concluded that most interpreters recognized Gen 4:26b as denoting the pronunciation of YHWH’s name, though other phenomena like participation in the YHWH cult were at times understood to be connoted. This meaning likely reflects the intent of the original author, who meant Gen 4:26b to serve as the introduction of the knowledge and use of YHWH’s name by characters. Gen 4:26b represented a tradition reflecting a cultural memory of a subgroup of Israelites who already worshipped YHWH before joining the Israelite coalition. Rival traditions reflecting the variant cultural memories of other groups are manifest in passages that seem to contradict Gen 4:26b like Exod 3:14-15 and Exod 6:2-3, though other programs are at work in each of these passages. Gen 4:26b was transposed from the beginning of what is now Gen 4 to its end when a “major redactor” combined its parent text with “Priestly material”, which obscured the original author’s programmatic intent to introduce the use of YHWH’s name by characters. The major redactor introduced a secondary program in place of this, whereby Gen 4:26b now contained the 70th mention of God and a culmination of Gen 1-4. Gen 4:26b was associated by most interpreters with Enosh, the character born in Gen 4:26a, immediately before. Attitudes towards Enosh, then, can serve as a proxy for the understood connotations of Gen 4:26b over time. These reveal a generally positive opinion of what occurred in Gen 4:26b in Second Temple Judaism and early Christianity, but a shift to negative assessments of Enosh in Rabbinic Judaism as an idolator. These most likely reflect the emergence of negative associations with pronouncing “YHWH” in virtually all contexts in Rabbinic Judaism. / Religion

OLIVEIRA, Ana Karolinna Maia de. Estudo de casos de complexidade de colorações gulosa de vértices e de arestas. 2011. 58 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2011. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-24T19:36:17Z No. of bitstreams: 1 2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-24T19:36:55Z (GMT) No. of bitstreams: 1 2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) / Made available in DSpace on 2016-05-24T19:36:55Z (GMT). No. of bitstreams: 1 2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) Previous issue date: 2011 / The vertices and edges colorings problems, which consists in determine the smallest number of colors needed to color the vertices and edges of a graph, respectively, so that adjacent vertices and adjacent edges, respectively, have distinct colors, are computationally hard problems and recurring subject of research in graph theory due to numerous practical problems they model. In this work, we study the worst performance of greedy algorithms for coloring vertices and edges. The greedy algorithm has the following general principle: to receive, one by one, the vertices (respect. edges) of the graph to be colored by assigning always the smallest possible color to the vertex (resp. edge) to be colored. We note that so greedy coloring the edges of a graph is equivalent to greedily coloring its line graph, this being the greatest interest in research on greedy edges coloring. The worst performance of the Algorithms is measured by the greatest number of colors they can use. In the case of greedy vertex coloring, this is the number of Grundy or greedy chromatic number of the graph. For the edge coloring, this is the greedy chromatic index or Grundy index of the graph. It is known that determining the Grundy number of any graph is NP-hard. The complexity of determining the Grundy index of any graph was however an open problem. In this dissertation, we prove two complexity results. We prove that the Grundy number of a (q,q−4)-graph can be determined in polynomial time. This class contains strictly the class of cografos P4-sparse for which the same result had been established. This result generalizes so those results. The presented algorithm uses the primeval decomposition of graphs, determining the parameter in linear time. About greedy edge coloring, we prove that the problem of determining the Grundy index is NP-complete for general graphs and polynomial for catepillar graphs, implying that the Grundy number is polynomial for graphs of line of caterpillars. More specifically, we prove that the Grundy index of a caterpillar is D or D+1 and present a polynomial algorithm to determine it exactly. / Os problemas de colorac¸ ˜ao de v´ertices e de arestas, que consistem em determinar o menor n´umero de cores necess´arias para colorir os v´ertices e arestas de um grafo, respectivamente, de forma que v´ertices adjacentes e arestas adjacentes, respectivamente, possuem cores distintas, s˜ao problemas computacionalmente dif´ıceis e s˜ao objeto de pesquisa recorrente em teoria do grafos em virtude de in´umeros problemas pr´aticos que eles modelam. No presente trabalho, estudamos o pior desempenho dos algoritmos gulosos de colorac¸ ˜ao de v´ertices e de arestas. O algoritmo guloso tem o seguinte princ´ıpio geral: receber, um a um, os v´ertices (respect. as arestas) do grafo a ser colorido, atribuindo sempre a menor cor poss´ıvel ao v´ertice (resp. aresta) a ser colorido. Observamos que colorir de forma gulosa as arestas de um grafo equivale a colorir de forma gulosa o seu grafo linha, tendo sido este o maior interesse na pesquisa em colorac¸ ˜ao gulosa de arestas. O pior desempenho dos algoritmos ´e medido pelo maior n´umero de cores que eles podem utilizar. No caso da colorac¸ ˜ao gulosa de v´ertices, esse ´e o n´umero de Grundy ou n´umero crom´atico guloso do grafo. No caso da colorac¸ ˜ao de arestas, esse ´e o ´ındice crom´atico guloso ou ´ındice de Grundy do grafo. Sabe-se que determinar o n´umero de Grundy de um grafo qualquer ´e NP-dif´ıcil. A complexidade de determinar o ´ındice de Grundy de um grafo qualquer era entretanto um problema em aberto. Na presente dissertac¸ ˜ao, provamos dois resultados de complexidade. Provamos que o n´umero de Grundy de um grafo (q,q−4) pode ser determinado em tempo polinomial. Essa classe cont´em estritamente a classe dos cografos e P4-esparsos para os quais o mesmo resultado havia sido estabelecido. Esse resultado generaliza portanto aqueles resultados. O algoritmo apresentado usa a decomposic¸˜ao primeval desses grafos, determinando o parˆametro em tempo linear. No que se refere `a colorac¸ ˜ao de arestas, provamos que o problema de determinar o ´ındice de Grundy ´e NP-completo para grafos em geral e polinomial para grafos caterpillar, implicando que o n´umero de Grundy ´e polinomial para os grafos linha desses. Mais especificamente provamos que o ´ındice de Grundy dos caterpillar ´e D ou D+1 e apresentamos um algoritmo polinomial para determin´a-lo exatamente.

OLIVEIRA, Ana Karolinna Maia de. Estudo de casos de complexidade de colorações gulosa de vértices e de arestas. 2011. 58 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2011. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T18:03:48Z No. of bitstreams: 1 2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-13T12:34:49Z (GMT) No. of bitstreams: 1 2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) / Made available in DSpace on 2016-07-13T12:34:49Z (GMT). No. of bitstreams: 1 2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) Previous issue date: 2011 / The vertices and edges colorings problems, which consists in determine the smallest number of colors needed to color the vertices and edges of a graph, respectively, so that adjacent vertices and adjacent edges, respectively, have distinct colors, are computationally hard problems and recurring subject of research in graph theory due to numerous practical problems they model. In this work, we study the worst performance of greedy algorithms for coloring vertices and edges. The greedy algorithm has the following general principle: to receive, one by one, the vertices (respect. edges) of the graph to be colored by assigning always the smallest possible color to the vertex (resp. edge) to be colored. We note that so greedy coloring the edges of a graph is equivalent to greedily coloring its line graph, this being the greatest interest in research on greedy edges coloring. The worst performance of the Algorithms is measured by the greatest number of colors they can use. In the case of greedy vertex coloring, this is the number of Grundy or greedy chromatic number of the graph. For the edge coloring, this is the greedy chromatic index or Grundy index of the graph. It is known that determining the Grundy number of any graph is NP-hard. The complexity of determining the Grundy index of any graph was however an open problem. In this dissertation, we prove two complexity results. We prove that the Grundy number of a (q,q−4)-graph can be determined in polynomial time. This class contains strictly the class of cografos P4-sparse for which the same result had been established. This result generalizes so those results. The presented algorithm uses the primeval decomposition of graphs, determining the parameter in linear time. About greedy edge coloring, we prove that the problem of determining the Grundy index is NP-complete for general graphs and polynomial for catepillar graphs, implying that the Grundy number is polynomial for graphs of line of caterpillars. More specifically, we prove that the Grundy index of a caterpillar is D or D+1 and present a polynomial algorithm to determine it exactly. / Os problemas de coloracão de vértices e de arestas, que consistem em determinar o menor número de cores necessárias para colorir os vértices e arestas de um grafo, respectivamente, de forma que vértices adjacentes e arestas adjacentes, respectivamente, possuem cores distintas, são problemas computacionalmente difíceis e são objeto de pesquisa recorrente em teoria do grafos em virtude de inúmeros problemas práticos que eles modelam. No presente trabalho, estudamos o pior desempenho dos algoritmos gulosos de coloração de vértices e de arestas. O algoritmo guloso tem o seguinte princípio geral: receber, um a um, os vértices (respect. as arestas) do grafo a ser colorido, atribuindo sempre a menor cor possível ao vértice (resp. aresta) a ser colorido. Observamos que colorir de forma gulosa as arestas de um grafo equivale a colorir de forma gulosa o seu grafo linha, tendo sido este o maior interesse na pesquisa em coloração gulosa de arestas. O pior desempenho dos algoritmos é medido pelo maior número de cores que eles podem utilizar. No caso da coloração gulosa de vértices, esse é o número de Grundy ou número cromático guloso do grafo. No caso da coloração de arestas, esse é o íındice cromático guloso ou íındice de Grundy do grafo. Sabe-se que determinar o número de Grundy de um grafo qualquer é NP-difícil. A complexidade de determinar o índice de Grundy de um grafo qualquer era entretanto um problema em aberto. Na presente dissertação, provamos dois resultados de complexidade. Provamos que o número de Grundy de um grafo (q,q−4) pode ser determinado em tempo polinomial. Essa classe contém estritamente a classe dos cografos e P4-esparsos para os quais o mesmo resultado havia sido estabelecido. Esse resultado generaliza portanto aqueles resultados. O algoritmo apresentado usa a decomposição primeval desses grafos, determinando o parâmetro em tempo linear. No que se refere à coloração de arestas, provamos que o problema de determinar o índice de Grundy é NP-completo para grafos em geral e polinomial para grafos caterpillar, implicando que o número de Grundy é polinomial para os grafos linha desses. Mais especificamente provamos que o índice de Grundy dos caterpillar é D ou D+1 e apresentamos um algoritmo polinomial para determiná-lo exatamente.

Georges Lemaître is quite unknown in Czech society. Although he was one of the scientists who independently anticipated the expansion of the cosmos and later formulated one of the most important hypotheses of the twentieth century - the hypothesis of the Primavel Atom, generally known as the Big Bang Theory as well as he was the president of The Pontifical Academy of Sciences, there has been published almost nothing about him in the Czech Republic. What was Lemaître's life like? What does his hypothesis mean in the context of Christian astronomical discourse of last centuries? How was his mission of the priest linked with work in astrophysics and mathematics?

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Os problemas de coloraÃÃo estÃo entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importÃncia teÃrica e prÃtica. O problema da L(2,1)-coloraÃÃo, por exemplo, pode ser aplicado na atribuiÃÃo de frequÃncias de rÃdio a torres de transmissÃo visando a diminuiÃÃo de interferÃncias nas transmissÃes. No entanto a maior parte das coloraÃÃes de Grafos à de difÃcil resoluÃÃo(NP-DifÃceis). Nesta dissertaÃÃo, estudamos os problemas de L(2,1)-coloraÃÃo, coloraÃÃo harmÃnica e M-partiÃÃo. Tendo em vista que os problemas de coloraÃÃo abordados nesta dissertaÃÃo sÃo todos NP-difÃceis, decidimos estudar as restriÃÃes destes problemas a (q,q-4)-grafos , com q fixo. As soluÃÃes utilizam a decomposiÃÃo primeval destes grafos. Ressaltamos ainda que esta classe contÃm os cografos e os grafos P4-esparsos. Os algoritmos encontrados desta maneira sÃo chamados de Fixed Parameter Tractable(FPT), pois sÃo polinomiais quando consideramos um determinado parÃmetro como um valor fixo. AlÃm da obtenÃÃo de algoritmos para diversos problemas de coloraÃÃo restritos aos (q,q-4)-grafos, com q fixo, tambÃm avaliamos a Conjectura de Griggs-Yeh com relaÃÃo aos grafos P_4-Esparsos e P_4-Laden. / The coloring problems are among the most studied in the graph theory due to its great theoretical and practical importance. The L(2;1)-labeling problem, for instance, can be applied to the frequency assignment of transmission towers in order to decrease interference in transmissions. However most of the graph coloring problems are difficult to solve (NP-hard). In this thesis, we study the L(2;1)-coloring, the harmonious coloring and M-partition of graphs. Considering that the coloring problems addressed in this thesis are all NP-hard, we decided to study the restrictions of these problems to (q;q􀀀4)-graphs, with q fixed. The solutions use the Primeval decomposition of these graphs. We also emphasize that this class contains the cographs and P4-sparse graphs. The algorithms found in this way are called Fixed parameter tractable (FPT), because they run on polynomial time if we consider a certain parameter as a fixed value. Besides obtaining algorithms for several coloring problems restricted to (q;q􀀀4)-graphs, with q fixed, we also evaluated Conjecture of Griggs-Yeh graphs with respect to P4-Sparse and P4-Laden graphs.

Je combine de nouveaux modèles de production de radiations stellaires et de transport radiatif à travers le milieu interstellaire (MI). Cela permet de caractériser les étoiles ainsi que le MI neutre et ionisé dans des galaxies formant des étoiles (GFE), via des raies ultraviolettes dans leur spectre. J'évalue la fiabilité des modèles stellaires en ajustant dans l'ultraviolet les indices d'absorption mesurés dans les spectres stellaires de 10 amas d'étoiles dans le Grand Nuage de Magellan. Je montre que négliger l'échantillonnage stochastique de la fonction de masse initiale stellaire de ces amas jeunes et peu massifs a une faible influence dans l'estimation d'âge et de métallicité, mais peut entraîner une surestimation significative des estimations de leur masse. Ensuite, je développe une approche basée sur une description épurée des principales caractéristiques du MI, afin de calculer de manière auto-cohérente l'influence combinée de l'émission et de l'absorption de ce milieu dans le spectre ultraviolet des GFE. Ce modèle tient compte du transport radiatif aussi bien à travers les couches intérieures ionisées, qu'à travers les couches extérieures neutres des nuages de formation d'étoiles ainsi que le milieu diffus entre ces nuages. J'utilise cette approche pour étudier la signature enchevêtrée des étoiles, du milieu neutre et du milieu ionisé dans les spectres ultraviolets des GFE. J'obtiens que la plupart des indices stellaires dans l'ultraviolet sont susceptibles de présenter une contamination par le MI qui augmente avec la métallicité. Enfin, j'identifie des raies d'émission et d'absorption interstellaires pouvant discriminer efficacement les différentes phases du MI. / I combine state-of-the-art models for the production of stellar radiation and its transfer through the interstellar medium (ISM) to investigate ultraviolet-line diagnostics of stars, the ionized and the neutral ISM in star-forming galaxies. I start by assessing the reliability of the stellar population synthesis modelling by fitting absorption-line indices in the ISM-free ultraviolet spectra of 10 Large-Magellanic-Cloud clusters. In doing so, I find that neglecting stochastic sampling of the stellar initial mass function in these young low-mass clusters affects negligibly ultraviolet-based age and metallicity estimates but can lead to significant overestimates of stellar mass. Then, I develop a simple approach, based on an idealized description of the main features of the ISM, to compute in a physically consistent way the combined influence of nebular emission and interstellar absorption on ultraviolet spectra of star-forming galaxies. My model accounts for the transfer of radiation through the ionized interiors and outer neutral envelopes of short-lived stellar birth clouds, as well as for radiative transfer through a diffuse intercloud medium. I use this approach to explore the entangled signatures of stars, the ionized and the neutral ISM in ultraviolet spectra of star-forming galaxies. I find that, aside from a few notable exceptions, most standard ultraviolet indices defined in the spectra of ISM-free stellar populations are prone to significant contamination by the ISM, which increases with metallicity. I also identify several nebular-emission and interstellar-absorption features, which stand out as particularly clean tracers of the different phases of the ISM.

No description available.

MARTINS, Nicolas de Almeida. Problemas de coloração de grafos com poucos P4´s. 2013. 53 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T14:47:13Z No. of bitstreams: 1 2013_dis_namartins.pdf: 515331 bytes, checksum: 2fe3c128ef3ee2889aa0c4a91d5fd916 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-20T12:11:19Z (GMT) No. of bitstreams: 1 2013_dis_namartins.pdf: 515331 bytes, checksum: 2fe3c128ef3ee2889aa0c4a91d5fd916 (MD5) / Made available in DSpace on 2016-07-20T12:11:19Z (GMT). No. of bitstreams: 1 2013_dis_namartins.pdf: 515331 bytes, checksum: 2fe3c128ef3ee2889aa0c4a91d5fd916 (MD5) Previous issue date: 2013 / The coloring problems are among the most studied in the graph theory due to its great theoretical and practical importance. The L(2;1)-labeling problem, for instance, can be applied to the frequency assignment of transmission towers in order to decrease interference in transmissions. However most of the graph coloring problems are difficult to solve (NP-hard). In this thesis, we study the L(2;1)-coloring, the harmonious coloring and M-partition of graphs. Considering that the coloring problems addressed in this thesis are all NP-hard, we decided to study the restrictions of these problems to (q;q4)-graphs, with q fixed. The solutions use the Primeval decomposition of these graphs. We also emphasize that this class contains the cographs and P4-sparse graphs. The algorithms found in this way are called Fixed parameter tractable (FPT), because they run on polynomial time if we consider a certain parameter as a fixed value. Besides obtaining algorithms for several coloring problems restricted to (q;q4)-graphs, with q fixed, we also evaluated Conjecture of Griggs-Yeh graphs with respect to P4-Sparse and P4-Laden graphs. / Os problemas de coloração estão entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importância teórica e prática. O problema da L(2,1)-coloração, por exemplo, pode ser aplicado na atribuição de frequências de rádio a torres de transmissão visando a diminuição de interferências nas transmissões. No entanto a maior parte das colorações de Grafos é de difícil resolução(NP-Difíceis). Nesta dissertação, estudamos os problemas de L(2,1)-coloração, coloração harmônica e M-partição. Tendo em vista que os problemas de coloração abordados nesta dissertação são todos NP-difíceis, decidimos estudar as restrições destes problemas a (q,q-4)-grafos , com q fixo. As soluções utilizam a decomposição primeval destes grafos. Ressaltamos ainda que esta classe contém os cografos e os grafos P4-esparsos. Os algoritmos encontrados desta maneira são chamados de Fixed Parameter Tractable(FPT), pois são polinomiais quando consideramos um determinado parâmetro como um valor fixo. Além da obtenção de algoritmos para diversos problemas de coloração restritos aos (q,q-4)-grafos, com q fixo, também avaliamos a Conjectura de Griggs-Yeh com relação aos grafos P_4-Esparsos e P_4-Laden.

No description available.