Videoaufnahmen aus den vergangenen Jahrzehnten stellen kulturelles Erbe dar. Diese sind jedoch nach heutigen Sehgewohnheiten nicht ohne große Einschränkungen für die Wiederausstrahlung geeignet. Das liegt zum einen an längst vergangenen Standards der Videoaufzeichnung, aber zum anderen auch in großem Maße an unkontrolliert gealterten Speichermedien durch inadäquate Aufbewahrung. Oftmals war es lokalen Fernsehsendern technisch nicht möglich ihre Archivbestände unter optimalen klimatischen Bedingungen langlebig zu lagern. Videoarchivdaten nach der Digitalisierung für die Einbindung in heutige Produktionen manuell zu durchsuchen und entsprechend aufzubereiten, ist ein zeitaufwändiger Prozess, den lokale TV-Sender nicht bewältigen können. In unserem Beitrag möchten wir neuartige Methoden der automatisierten Aufbereitung von archivierten VHS-Digitalisaten für die Wiederausstrahlung vorstellen. Dazu zählen vor allem Verfahren zu den Schwerpunkten der Korrektur von Falschfarben (Recoloring) und zur Steigerung der Auflösung von ehemals PAL zu Full-HD und Ultra-HD (Super-Resolution). Zum Einsatz kommen dabei künstliche neuronale Netze, die anders als klassische Verfahren der Bildverarbeitung, semantische Bildkomponenten erfassen und bei der Bearbeitung berücksichtigen können. Mitunter können so deutliche Qualitätsverbesserungen erzielt werden. In unserem Beitrag möchten wir auf Chancen und aktuelle Beschränkungen dieser Technologien eingehen und anhand von digitalisierten Videoarchivdaten deren Funktionsweise demonstrieren.

O foco central desta tese é o desenvolvimento de algoritmos para o problema de recoloração convexa de caminhos. Neste problema, é dado um caminho cujos vértices estão coloridos arbitrariamente, e o objetivo é recolorir o menor número possível de vértices de modo a obter uma coloração convexa. Dizemos que uma coloração de um grafo é convexa se, para cada cor, o subgrafo induzido pelos vértices dessa cor é conexo. Sabe-se que este problema é NP-difícil. Associamos a este problema um poliedro, e estudamos sua estrutura facial, com vistas ao desenvolvimento de um algoritmo. Mostramos várias inequações válidas para este poliedro, e provamos que várias delas definem facetas. Apresentamos um algoritmo de programação dinâmica que resolve em tempo polinomial o problema da separação para uma classe grande de inequações que definem facetas. Implementamos um algoritmo branch-and-cut baseado nesses resultados, e realizamos testes computacionais com instâncias geradas aleatoriamente. Apresentamos adicionalmente uma heurística baseada numa formulação linear que obtivemos. Estudamos também um caso especial deste problema, no qual as instâncias consistem em caminhos coloridos, onde cada cor ocorre no máximo duas vezes. Apresentamos um algoritmo de 3/2-aproximação para este caso, que é também NP-difícil. Para o caso geral, é conhecido na literatura um algoritmo de 2-aproximação. / The focus of this thesis is the design of algorithms for the convex recoloring problem on paths. In this problem, the instance consists of a path whose vertices are arbitrarily colored, and the objective is to recolor the least number of vertices so as to obtain a convex coloring.Acoloring of a graph is convex if, for each color, the subgraph induced by the vertices of this color is connected. This problem is known to be NP-hard. We associate a polyhedron to this problem and investigate its facial structure. We show various classes of valid inequalities for this polyhedron and prove that many of them define facets.We present a polynomial-time dynamic programming algorithm that solves, in polynomial time, the separation problem for a large class of facet-defining inequalities.We report on the computational experiments with a branch-and-cut algorithm that we propose for the problem. Additionally, we present a heuristic that is based on a linear formulation for the problem. We also study a special case of this problem, restricted to instances consisting of colored paths in which each color occurs at most twice. For this case, which is also NP-hard, we present a 3/2-approximation algorithm. For the general case, it is known a 2-approximation algorithm.

O foco central desta tese é o desenvolvimento de algoritmos para o problema de recoloração convexa de caminhos. Neste problema, é dado um caminho cujos vértices estão coloridos arbitrariamente, e o objetivo é recolorir o menor número possível de vértices de modo a obter uma coloração convexa. Dizemos que uma coloração de um grafo é convexa se, para cada cor, o subgrafo induzido pelos vértices dessa cor é conexo. Sabe-se que este problema é NP-difícil. Associamos a este problema um poliedro, e estudamos sua estrutura facial, com vistas ao desenvolvimento de um algoritmo. Mostramos várias inequações válidas para este poliedro, e provamos que várias delas definem facetas. Apresentamos um algoritmo de programação dinâmica que resolve em tempo polinomial o problema da separação para uma classe grande de inequações que definem facetas. Implementamos um algoritmo branch-and-cut baseado nesses resultados, e realizamos testes computacionais com instâncias geradas aleatoriamente. Apresentamos adicionalmente uma heurística baseada numa formulação linear que obtivemos. Estudamos também um caso especial deste problema, no qual as instâncias consistem em caminhos coloridos, onde cada cor ocorre no máximo duas vezes. Apresentamos um algoritmo de 3/2-aproximação para este caso, que é também NP-difícil. Para o caso geral, é conhecido na literatura um algoritmo de 2-aproximação. / The focus of this thesis is the design of algorithms for the convex recoloring problem on paths. In this problem, the instance consists of a path whose vertices are arbitrarily colored, and the objective is to recolor the least number of vertices so as to obtain a convex coloring.Acoloring of a graph is convex if, for each color, the subgraph induced by the vertices of this color is connected. This problem is known to be NP-hard. We associate a polyhedron to this problem and investigate its facial structure. We show various classes of valid inequalities for this polyhedron and prove that many of them define facets.We present a polynomial-time dynamic programming algorithm that solves, in polynomial time, the separation problem for a large class of facet-defining inequalities.We report on the computational experiments with a branch-and-cut algorithm that we propose for the problem. Additionally, we present a heuristic that is based on a linear formulation for the problem. We also study a special case of this problem, restricted to instances consisting of colored paths in which each color occurs at most twice. For this case, which is also NP-hard, we present a 3/2-approximation algorithm. For the general case, it is known a 2-approximation algorithm.

As Deficiências na Percepção de Cores (DPC) afetam aproximadamente 200 milhões de pessoas em todo o mundo, comprometendo suas habilidades para efetivamente realizar tarefas relacionadas com cores e com visualização. Isto impacta significantemente os âmbitos pessoais e profissionais de suas vidas. Este trabalho apresenta um modelo baseado na fisiologia para simulação da percepção de cores. Além de modelar visão de cores normal, ele também compreende os tipos mais predominantes de deficiências na visão de cores (i.e., protanopia, deuteranopia, protanomalia e deuteranomalia), cujas causas são hereditárias. Juntos estes representam aproximadamente 99.96% de todos os casos de DPC. Para modelar a percepção de cores da visão humana, este modelo é baseado na teoria dos estágios e é derivado de dados reportados em estudos eletrofisiológicos. Ele é o primeiro modelo a consistentemente tratar visão de cores normal, tricromacia anômala e dicromacia de modo unificados. Seus resultados foram validados por avaliações experimentais envolvendo grupos de indivíduos com deficiência na percepção de cores e outros com visão de cores normal. Além disso, ele pode proporcionar a melhor compreensão e um feedback sobre como aperfeiçoar as experiências de visualização por indivíduos com DPC. Ele também proporciona um framework para se testar hipóteses sobre alguns aspectos acerca das células fotoreceptoras na retina de indivíduos com deficiência na percepção de cores. Este trabalho também apresenta uma técnica automática de recoloração de imagens que visa realçar o contraste de cores para indivíduos dicromatas com custo computacional variando linearmente com o número de pixels. O algoritmo proposto pode ser eficientemente implementado em GPUs, e para imagens com tamanhos tipicos ele apresenta performance de até duas ordens de magnitude mais rápida do que as técnicas estado da arte atuais. Ao contrário das abordagens anteriores, a técnica proposta preserva coerência temporal e, portanto, é adequado para recoloração de vídeos. Este trabalho demonstra a efetividade da técnica proposta ao integrá-la a um sistema de visualização e apresentando, pela primeira vez, cenas de visualização recoloridas para dicromatas em tempo-real e com alta qualidade. / Color vision deficiency (CVD) affects approximately 200 million people worldwide, compromising the ability of these individuals to effectively perform color and visualizationrelated tasks. This has a significant impact on their private and professional lives. This thesis presents a physiologically-based model for simulating color perception. Besides modeling normal color vision, it also accounts for the hereditary and most prevalent cases of color vision deficiency (i.e., protanopia, deuteranopia, protanomaly, and deuteranomaly), which together account for approximately 99.96% of all CVD cases. This model is based on the stage theory of human color vision and is derived from data reported in electrophysiological studies. It is the first model to consistently handle normal color vision, anomalous trichromacy, and dichromacy in a unified way. The proposed model was validated through an experimental evaluation involving groups of color vision deficient individuals and normal color vision ones. This model can provide insights and feedback on how to improve visualization experiences for individuals with CVD. It also provides a framework for testing hypotheses about some aspects of the retinal photoreceptors in color vision deficient individuals. This thesis also presents an automatic image-recoloring technique for enhancing color contrast for dichromats whose computational cost varies linearly with the number of input pixels. This approach can be efficiently implemented on GPUs, and for typical image sizes it is up to two orders of magnitude faster than the current state-of-the-art technique. Unlike previous approaches, the proposed technique preserves temporal coherence and, therefore, is suitable for video recoloring. This thesis demonstrates the effectiveness of the proposed technique by integrating it into a visualization system and showing, for the first time, real-time high-quality recolored visualizations for dichromats.

As Deficiências na Percepção de Cores (DPC) afetam aproximadamente 200 milhões de pessoas em todo o mundo, comprometendo suas habilidades para efetivamente realizar tarefas relacionadas com cores e com visualização. Isto impacta significantemente os âmbitos pessoais e profissionais de suas vidas. Este trabalho apresenta um modelo baseado na fisiologia para simulação da percepção de cores. Além de modelar visão de cores normal, ele também compreende os tipos mais predominantes de deficiências na visão de cores (i.e., protanopia, deuteranopia, protanomalia e deuteranomalia), cujas causas são hereditárias. Juntos estes representam aproximadamente 99.96% de todos os casos de DPC. Para modelar a percepção de cores da visão humana, este modelo é baseado na teoria dos estágios e é derivado de dados reportados em estudos eletrofisiológicos. Ele é o primeiro modelo a consistentemente tratar visão de cores normal, tricromacia anômala e dicromacia de modo unificados. Seus resultados foram validados por avaliações experimentais envolvendo grupos de indivíduos com deficiência na percepção de cores e outros com visão de cores normal. Além disso, ele pode proporcionar a melhor compreensão e um feedback sobre como aperfeiçoar as experiências de visualização por indivíduos com DPC. Ele também proporciona um framework para se testar hipóteses sobre alguns aspectos acerca das células fotoreceptoras na retina de indivíduos com deficiência na percepção de cores. Este trabalho também apresenta uma técnica automática de recoloração de imagens que visa realçar o contraste de cores para indivíduos dicromatas com custo computacional variando linearmente com o número de pixels. O algoritmo proposto pode ser eficientemente implementado em GPUs, e para imagens com tamanhos tipicos ele apresenta performance de até duas ordens de magnitude mais rápida do que as técnicas estado da arte atuais. Ao contrário das abordagens anteriores, a técnica proposta preserva coerência temporal e, portanto, é adequado para recoloração de vídeos. Este trabalho demonstra a efetividade da técnica proposta ao integrá-la a um sistema de visualização e apresentando, pela primeira vez, cenas de visualização recoloridas para dicromatas em tempo-real e com alta qualidade. / Color vision deficiency (CVD) affects approximately 200 million people worldwide, compromising the ability of these individuals to effectively perform color and visualizationrelated tasks. This has a significant impact on their private and professional lives. This thesis presents a physiologically-based model for simulating color perception. Besides modeling normal color vision, it also accounts for the hereditary and most prevalent cases of color vision deficiency (i.e., protanopia, deuteranopia, protanomaly, and deuteranomaly), which together account for approximately 99.96% of all CVD cases. This model is based on the stage theory of human color vision and is derived from data reported in electrophysiological studies. It is the first model to consistently handle normal color vision, anomalous trichromacy, and dichromacy in a unified way. The proposed model was validated through an experimental evaluation involving groups of color vision deficient individuals and normal color vision ones. This model can provide insights and feedback on how to improve visualization experiences for individuals with CVD. It also provides a framework for testing hypotheses about some aspects of the retinal photoreceptors in color vision deficient individuals. This thesis also presents an automatic image-recoloring technique for enhancing color contrast for dichromats whose computational cost varies linearly with the number of input pixels. This approach can be efficiently implemented on GPUs, and for typical image sizes it is up to two orders of magnitude faster than the current state-of-the-art technique. Unlike previous approaches, the proposed technique preserves temporal coherence and, therefore, is suitable for video recoloring. This thesis demonstrates the effectiveness of the proposed technique by integrating it into a visualization system and showing, for the first time, real-time high-quality recolored visualizations for dichromats.

As Deficiências na Percepção de Cores (DPC) afetam aproximadamente 200 milhões de pessoas em todo o mundo, comprometendo suas habilidades para efetivamente realizar tarefas relacionadas com cores e com visualização. Isto impacta significantemente os âmbitos pessoais e profissionais de suas vidas. Este trabalho apresenta um modelo baseado na fisiologia para simulação da percepção de cores. Além de modelar visão de cores normal, ele também compreende os tipos mais predominantes de deficiências na visão de cores (i.e., protanopia, deuteranopia, protanomalia e deuteranomalia), cujas causas são hereditárias. Juntos estes representam aproximadamente 99.96% de todos os casos de DPC. Para modelar a percepção de cores da visão humana, este modelo é baseado na teoria dos estágios e é derivado de dados reportados em estudos eletrofisiológicos. Ele é o primeiro modelo a consistentemente tratar visão de cores normal, tricromacia anômala e dicromacia de modo unificados. Seus resultados foram validados por avaliações experimentais envolvendo grupos de indivíduos com deficiência na percepção de cores e outros com visão de cores normal. Além disso, ele pode proporcionar a melhor compreensão e um feedback sobre como aperfeiçoar as experiências de visualização por indivíduos com DPC. Ele também proporciona um framework para se testar hipóteses sobre alguns aspectos acerca das células fotoreceptoras na retina de indivíduos com deficiência na percepção de cores. Este trabalho também apresenta uma técnica automática de recoloração de imagens que visa realçar o contraste de cores para indivíduos dicromatas com custo computacional variando linearmente com o número de pixels. O algoritmo proposto pode ser eficientemente implementado em GPUs, e para imagens com tamanhos tipicos ele apresenta performance de até duas ordens de magnitude mais rápida do que as técnicas estado da arte atuais. Ao contrário das abordagens anteriores, a técnica proposta preserva coerência temporal e, portanto, é adequado para recoloração de vídeos. Este trabalho demonstra a efetividade da técnica proposta ao integrá-la a um sistema de visualização e apresentando, pela primeira vez, cenas de visualização recoloridas para dicromatas em tempo-real e com alta qualidade. / Color vision deficiency (CVD) affects approximately 200 million people worldwide, compromising the ability of these individuals to effectively perform color and visualizationrelated tasks. This has a significant impact on their private and professional lives. This thesis presents a physiologically-based model for simulating color perception. Besides modeling normal color vision, it also accounts for the hereditary and most prevalent cases of color vision deficiency (i.e., protanopia, deuteranopia, protanomaly, and deuteranomaly), which together account for approximately 99.96% of all CVD cases. This model is based on the stage theory of human color vision and is derived from data reported in electrophysiological studies. It is the first model to consistently handle normal color vision, anomalous trichromacy, and dichromacy in a unified way. The proposed model was validated through an experimental evaluation involving groups of color vision deficient individuals and normal color vision ones. This model can provide insights and feedback on how to improve visualization experiences for individuals with CVD. It also provides a framework for testing hypotheses about some aspects of the retinal photoreceptors in color vision deficient individuals. This thesis also presents an automatic image-recoloring technique for enhancing color contrast for dichromats whose computational cost varies linearly with the number of input pixels. This approach can be efficiently implemented on GPUs, and for typical image sizes it is up to two orders of magnitude faster than the current state-of-the-art technique. Unlike previous approaches, the proposed technique preserves temporal coherence and, therefore, is suitable for video recoloring. This thesis demonstrates the effectiveness of the proposed technique by integrating it into a visualization system and showing, for the first time, real-time high-quality recolored visualizations for dichromats.

The vertex coloring problem is a classic problem in graph theory that asks for a partition of the vertex set into a minimum number of stable sets. This thesis presents our studies on three vertex (re)coloring problems on graphs and on a problem related to a long-standing conjecture on subdivision of digraphs. Firstly, we address the convex recoloring problem in which an arbitrarily colored graph G is given and one wishes to find a minimum weight recoloring such that each color class induces a connected subgraph of G. We show inapproximability results, introduce an integer linear programming (ILP) formulation that models the problem and present some computational experiments using a column generation approach. The k-fold coloring problem is a generalization of the classic vertex coloring problem and consists in covering the vertex set of a graph by a minimum number of stable sets in such a way that every vertex is covered by at least k (possibly identical) stable sets. We present an ILP formulation for this problem and show a detailed polyhedral study of the polytope associated with this formulation. The last coloring problem studied in this thesis is the proper orientation problem. It consists in orienting the edge set of a given graph so that adjacent vertices have different in-degrees and the maximum in-degree is minimized. Clearly, the in-degrees induce a partition of the vertex set into stable sets, that is, a coloring (in the conventional sense) of the vertices. Our contributions in this problem are on hardness and upper bounds for bipartite graphs. Finally, we study a problem related to a conjecture of Mader from the eighties on subdivision of digraphs. This conjecture states that, for every acyclic digraph H, there exists an integer f(H) such that every digraph with minimum out-degree at least f(H) contains a subdivision of H as a subdigraph. We show evidences for this conjecture by proving that it holds for some particular classes of acyclic digraphs. / O problema de coloração de grafos é um problema clássico em teoria dos grafos cujo objetivo é particionar o conjunto de vértices em um número mínimo de conjuntos estáveis. Nesta tese apresentamos nossas contribuições sobre três problemas de coloração de grafos e um problema relacionado a uma antiga conjectura sobre subdivisão de digrafos. Primeiramente, abordamos o problema de recoloração convexa no qual é dado um grafo arbitrariamente colorido G e deseja-se encontrar uma recoloração de peso mínimo tal que cada classe de cor induza um subgrafo conexo de G. Mostramos resultados sobre inaproximabilidade, introduzimos uma formulação linear inteira que modela esse problema, e apresentamos alguns resultados computacionais usando uma abordagem de geração de colunas. O problema de k-upla coloração é uma generalização do problema clássico de coloração de vértices e consiste em cobrir o conjunto de vértices de um grafo com uma quantidade mínima de conjuntos estáveis de tal forma que cada vértice seja coberto por pelo menos k conjuntos estáveis (possivelmente idênticos). Apresentamos uma formulação linear inteira para esse problema e fazemos um estudo detalhado do politopo associado a essa formulação. O último problema de coloração estudado nesta tese é o problema de orientação própria. Ele consiste em orientar o conjunto de arestas de um dado grafo de tal forma que vértices adjacentes possuam graus de entrada distintos e o maior grau de entrada seja minimizado. Claramente, os graus de entrada induzem uma partição do conjunto de vértices em conjuntos estáveis, ou seja, induzem uma coloração (no sentido convencional) dos vértices. Nossas contribuições nesse problema são em complexidade computacional e limitantes superiores para grafos bipartidos. Finalmente, estudamos um problema relacionado a uma conjectura de Mader, dos anos oitenta, sobre subdivisão de digrafos. Esta conjectura afirma que, para cada digrafo acíclico H, existe um inteiro f(H) tal que todo digrafo com grau mínimo de saída pelo menos f(H) contém uma subdivisão de H como subdigrafo. Damos evidências para essa conjectura mostrando que ela é válida para classes particulares de digrafos acíclicos.

Color vision deficiency (CVD) is the inability or limited ability to recognize colors and discriminate between them. A person with this condition perceives a narrower range of colors compared to a person with a normal color vision. A growing number of researchers are striving to improve the quality of life for CVD patients. Finding cure, making rectification equipment, providing simulation tools and applying color transformation methods are among the efforts being made by researchers in this field. In this study we concentrate on recoloring digital images in such a way that users with CVD, especially dichromats, perceive more details from the recolored images compared to the original image. The main focus is to give the CVD user a chance to find information within the picture which they could not perceive before. However, this transformed image might look strange or unnatural to users with normal color vision. During this color transformation process, the goal is to keep the overall contrast of the image constant while adjusting the colors that might cause confusion for the CVD user. First, each pixel in the RGB-image is converted to HSV color space in order to be able to control hue, saturation and intensity for each pixel and then safe and problematic hue ranges need to be found. The method for recognizing these ranges was inspired by a condition called “unilateral dichromacy” in which the patient has normal color vision in one eye and dichromacy in another. A special grid-like color card is designed, having constant saturation and intensity over the entire image, while the hue smoothly changes from one block to another to cover the entire hue range. The next step is to simulate the way this color card is perceived by a dichromatic user and finally to find the colors that are perceived identically from two images and the ones that differ too much. This part makes our method highly customizable and we can apply it to other types of CVD, even personalize it for the color vision of a specific observer. The resulting problematic colors need to be dealt with by shifting the hue or saturation based on some pre-defined rules. The results for the method have been evaluated both objectively and subjectively. First, we simulated a set of images as they would be perceived by a dichromat and compared them with simulated view of our transformed images. The results clearly show that our recolored images can eliminate a lot of confusion from user and convey more details. Moreover, an online questionnaire was created and 39 users with CVD confirmed that the transformed images allow them to perceive more information compared to the original images.

The vertex coloring problem is a classic problem in graph theory that asks for a partition of the vertex set into a minimum number of stable sets. This thesis presents our studies on three vertex (re)coloring problems on graphs and on a problem related to a long-standing conjecture on subdivision of digraphs. Firstly, we address the convex recoloring problem in which an arbitrarily colored graph G is given and one wishes to find a minimum weight recoloring such that each color class induces a connected subgraph of G. We show inapproximability results, introduce an integer linear programming (ILP) formulation that models the problem and present some computational experiments using a column generation approach. The k-fold coloring problem is a generalization of the classic vertex coloring problem and consists in covering the vertex set of a graph by a minimum number of stable sets in such a way that every vertex is covered by at least k (possibly identical) stable sets. We present an ILP formulation for this problem and show a detailed polyhedral study of the polytope associated with this formulation. The last coloring problem studied in this thesis is the proper orientation problem. It consists in orienting the edge set of a given graph so that adjacent vertices have different in-degrees and the maximum in-degree is minimized. Clearly, the in-degrees induce a partition of the vertex set into stable sets, that is, a coloring (in the conventional sense) of the vertices. Our contributions in this problem are on hardness and upper bounds for bipartite graphs. Finally, we study a problem related to a conjecture of Mader from the eighties on subdivision of digraphs. This conjecture states that, for every acyclic digraph H, there exists an integer f(H) such that every digraph with minimum out-degree at least f(H) contains a subdivision of H as a subdigraph. We show evidences for this conjecture by proving that it holds for some particular classes of acyclic digraphs. / O problema de coloração de grafos é um problema clássico em teoria dos grafos cujo objetivo é particionar o conjunto de vértices em um número mínimo de conjuntos estáveis. Nesta tese apresentamos nossas contribuições sobre três problemas de coloração de grafos e um problema relacionado a uma antiga conjectura sobre subdivisão de digrafos. Primeiramente, abordamos o problema de recoloração convexa no qual é dado um grafo arbitrariamente colorido G e deseja-se encontrar uma recoloração de peso mínimo tal que cada classe de cor induza um subgrafo conexo de G. Mostramos resultados sobre inaproximabilidade, introduzimos uma formulação linear inteira que modela esse problema, e apresentamos alguns resultados computacionais usando uma abordagem de geração de colunas. O problema de k-upla coloração é uma generalização do problema clássico de coloração de vértices e consiste em cobrir o conjunto de vértices de um grafo com uma quantidade mínima de conjuntos estáveis de tal forma que cada vértice seja coberto por pelo menos k conjuntos estáveis (possivelmente idênticos). Apresentamos uma formulação linear inteira para esse problema e fazemos um estudo detalhado do politopo associado a essa formulação. O último problema de coloração estudado nesta tese é o problema de orientação própria. Ele consiste em orientar o conjunto de arestas de um dado grafo de tal forma que vértices adjacentes possuam graus de entrada distintos e o maior grau de entrada seja minimizado. Claramente, os graus de entrada induzem uma partição do conjunto de vértices em conjuntos estáveis, ou seja, induzem uma coloração (no sentido convencional) dos vértices. Nossas contribuições nesse problema são em complexidade computacional e limitantes superiores para grafos bipartidos. Finalmente, estudamos um problema relacionado a uma conjectura de Mader, dos anos oitenta, sobre subdivisão de digrafos. Esta conjectura afirma que, para cada digrafo acíclico H, existe um inteiro f(H) tal que todo digrafo com grau mínimo de saída pelo menos f(H) contém uma subdivisão de H como subdigrafo. Damos evidências para essa conjectura mostrando que ela é válida para classes particulares de digrafos acíclicos.