Decomposições para coloração de arestas e coloração total de grafos

220 f. : il., tab.Esta tese propõe a aplicação a coloração de arestas e coloração total de técnicas já consolidadas no contexto de coloração de vértices. Aplicamos tais técnicas de forma a obter resultados de complexidade de coloração de arestas e coloração total restritos a classes de grafos, tais como grafos join, grafos cobipartidos, partial-grids, grafos outerplanares, grafos chordless, grafos unichord-free, bipartidos unichord-free e fsquare,unichordg-free. Os resultados obtidos mostram a independência entre os problemas de coloração de arestas e de coloração total e permitem compreender melhor a relação e as distinções entre estes problemas clássicos de coloração. ____________________________________________________________________________________.ABSTRACT: The present thesis considers the application to edge-colouring and total-colouring of decomposition techniques well established in the vertex-colouring scenario. We apply such decomposition techniques to obtain complexity results for edge-colouring and total-colouring in graph classes, such as join graphs, cobipartite graphs,partial-grids, outerplanar graphs, chordless graphs, unichord-free graphs, bipartite unichord-free graphs, and fsquare,unichordg-free graphs. The obtained results allow a better undertanding on the relations | and distinctions | between these classical graph colouring problems