Coloração de arestas em grafos indiferença
Flavio de Freitas Stecca
DISSERTAÇÃO
Português
(Broch.)
T/UNICAMP St31c
Campinas, SP : [s.n.], 2003.
79f.
Orientador: João Meidanis
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Resumo: Esta dissertação aborda o problema da coloração de arestas restrito aos grafos indiferença. O teorema de Vizing diz que qualquer grafo pode ter suas arestas coloridas com .6 (G) ou .6( G) + 1 cores. Grafos pertencentes à Classe 1 são os grafos cujo índice cromático (n úmero mínimo de cores...
Ver mais
Resumo: Esta dissertação aborda o problema da coloração de arestas restrito aos grafos indiferença. O teorema de Vizing diz que qualquer grafo pode ter suas arestas coloridas com .6 (G) ou .6( G) + 1 cores. Grafos pertencentes à Classe 1 são os grafos cujo índice cromático (n úmero mínimo de cores suficientes para pintar suas arestas) X' é igual a .6 ( G) . Se X' = .6(G) + 1, o grafo pertence à Classe 2. Um grafo é dito overfull se .6(G) l_J < m, onde nem são o número de vértices e o número de arestas, respectivamente. Grafos neighborhood overfull são grafos que têm um vértice de grau máximo cuja vizinhança induz um subgrafo overfull. Grafos indiferença overfull ou neighborhood overfull pertencem à Classe 2. Apresentaremos uma breve compilação de resultados de pesquisas. Dois destes resultados mostram que grafos indiferença com grau máximo ímpar e grafos indiferença reduzidos pertencem à Classe 1, porém o problema ainda está em aberto para um grafo indiferença qualquer. Abordamos o problema criando um modelo de programação linear para coloração de arestas. Implementamos um gerador que nos permitiu gerar grafos indiferença de dife-rentes estruturas. Estes grafos tiveram suas arestas coloridas através de programação linear. Definimos um tipo especial de grafo indiferença denominado grafo indiferença semi-universal. Criamos um método que permite cobrir um grafo indiferença com grafos indiferença semi-universais. Mostramos que resolver o problema para um grafo indife-rença qualquer equivale a estender certas colorações parciais para um grafo indiferença semi-universal qualquer. Reforçamos a conjectura de que todos os grafos indiferença não neighborhood overfull são Classe 1, através de testes práticos em milhares de grafos indi-ferença
Ver menos
Abstract: This dissertation is on the subject of edge coloring restricted to indifference graphs. Vi-zing's theorem states that any graph can be edge-colored with .6. or .6. + 1 colors. Graphs are said to be Class 1 if their chromatic index (minimum number of colors required to produce an...
Ver mais
Abstract: This dissertation is on the subject of edge coloring restricted to indifference graphs. Vi-zing's theorem states that any graph can be edge-colored with .6. or .6. + 1 colors. Graphs are said to be Class 1 if their chromatic index (minimum number of colors required to produce an edge-coloring) X ' equals .6.( G). If X ' = .6.( G) + 1 the graph is said to be Class 2. A graph is overfull if .6. (G) l _ J < m, where n and m are the number of vertices and number of edges, respectively. Graphs are said to be neighborhood overfull if they have a maximum-degree vertex whose neighborhood induces an overfull subgraph. Overfull and neighborhood overfull indifference graphs are Class 2. vVe will show a brief compilation of research results. Two of these results show that indifference graphs with odd maximum degree and reduced indifference graphs are Class 1, however the problem is open for a generic interference graph. The approach used for the problem was the creation of a linear programming mo dei for edge coloring. A graph generator program that allowed creation of indifference graphs with different structures was implemented. These graphs were edge colored using linear programming. We defined a special type of graph called semi-universal indifference graph. We created a method for covering an indifference graph with semi-universal indifference graphs. We show that solving the problem for indifference graphs is equivalent to ex-tending a partial edge coloring in a semi-universal indifference graph. We reinforce the conjecture that says that all indifference graphs not neighborhood overfull are Class 1, through practical tests in thousands of indifference graphs
Ver menos
Coloração de arestas em grafos indiferença
Flavio de Freitas Stecca
Coloração de arestas em grafos indiferença
Flavio de Freitas Stecca
Exemplares
Nº de exemplares: 2
Não existem reservas para esta obra