Decomposições para Coloração de Arestas e Coloração Total de Grafos
Autores
|
4729 |
257,2092
|
|
|
4730 |
257,2092
|
Informações:
Publicações do PESC
Esta tese propõe o uso de técnicas já consolidadas no contexto de coloração de vértices com o objetivo de melhor compreender os problemas de coloração de arestas e coloração total. 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 {square,unichord}-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.
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 {square,unichord}-free graphs. The obtained results allow a better undertanding on the relations - and distinctions - between these classical graph colouring problems.