dc.contributor.author | Cruz, Jadder Bismarck de Sousa | |
dc.date.accessioned | 2017-10-09T16:27:11Z | |
dc.date.available | 2017-10-09T16:27:11Z | |
dc.date.issued | 2017-05-02 | |
dc.identifier.citation | CRUZ, Jadder Bismarck de Sousa. Coloração de Arestas em Grafos Split-Comparabilidade. 2017. Dissertação (Mestrado em Ciência da Computação) – Universidade Federal de São Carlos, Sorocaba, 2017. Disponível em: https://repositorio.ufscar.br/handle/ufscar/9140. | * |
dc.identifier.uri | https://repositorio.ufscar.br/handle/ufscar/9140 | |
dc.description.abstract | Let G = (V, E) be a simple and undirected graph. An edge-coloring is an assignment of colors to the edges of the graph such that any two adjacent edges receive different colors. The chromatic index of a graph G is the smallest number of colors such that G has an edge-coloring. Clearly, a lower bound for the chromatic index is the degree of the vertex of higher degree, denoted by ?(G). In 1964, Vizing proved that chromatic index is ?(G) or ?(G) + 1. The Classification Problem is to determine if the chromatic index is ?(G) (Class 1 ) or if it is ?(G) + 1 (Class 2 ). Let n be number of vertices of a graph G and let m be its number of edges. We say G is overfull if m > (n-1) 2 ?(G). Every overfull graph is Class 2. A graph is subgraph-overfull if it has a subgraph with same maximum degree and it is overfull. It is well-known that every overfull and subgraph-overfull graph is Class 2. The Overfull Conjecture asserts that every graph with ?(G) > n 3 is Class 2 if and only if it is subgraph-overfull. In this work we prove the Overfull Conjecture to a particular class of graphs, known as split-comparability graphs. The Overfull Conjecture was open to this class. | eng |
dc.description.sponsorship | Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) | por |
dc.language.iso | por | por |
dc.publisher | Universidade Federal de São Carlos | por |
dc.rights.uri | Acesso aberto | por |
dc.subject | Teoria dos grafos | por |
dc.subject | Graph theory | eng |
dc.subject | Coloração de arestas | por |
dc.subject | Problema da Classificação | por |
dc.subject | Grafos split | eng |
dc.subject | Grafos comparabilidade | por |
dc.subject | Edge coloring | eng |
dc.subject | Chromatic index | eng |
dc.subject | Classification Problem | por |
dc.subject | Split graphs | eng |
dc.subject | Comparability graphs | eng |
dc.title | Coloração de Arestas em Grafos Split-Comparabilidade | por |
dc.title.alternative | Edge coloring in split-comparability graphs | eng |
dc.type | Dissertação | por |
dc.contributor.advisor1 | Silva, Cândida Nunes da | |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/6019111128413167 | por |
dc.contributor.advisor-co1 | Almeida, Sheila Morais de | |
dc.contributor.advisor-co1Lattes | http://lattes.cnpq.br/9151881548763857 | por |
dc.description.resumo | Dado um grafo simples e não direcionado G = (V, E), uma coloração de arestas é uma função que atribui cores às arestas do grafo tal que todas as arestas que incidem em um mesmo vértice têm cores distintas. O índice cromático é o número mínimo de cores para obter uma coloração própria das arestas de um grafo. Um limite inferior para o índice cromático é, claramente, o grau do vértice de maior grau, denotado por ?(G). Em 1964, Vizing provou que o índice cromático ou é ?(G) ou ?(G) + 1, surgindo assim o Problema da Classificação, que consiste em determinar se o índice cromático é ?(G) (Classe 1 ) ou ?(G) + 1 (Classe 2 ). Seja n o número de vértices de um grafo G e m seu número de arestas. Dizemos que um grafo é sobrecarregado se m > (n-1) 2 ?(G). Um grafo é subgrafo-sobrecarregado se tem um subgrafo de mesmo grau máximo que é sobrecarregado. É sabido que se um grafo é sobrecarregado ou subgrafo-sobrecarregado ele é necessariamente Classe 2. A Conjectura Overfull é uma famosa conjectura de coloração de arestas e diz que um grafo com ?(G) > n 3 é Classe 2 se e somente se é subgrafo-sobrecarregado. Neste trabalho provamos a Conjectura Overfull para uma classe de grafos, a classe dos grafos split-comparabilidade. Até este momento a Conjectura Overfull estava aberta para esta classe. | por |
dc.publisher.initials | UFSCar | por |
dc.publisher.program | Programa de Pós-Graduação em Ciência da Computação - PPGCC-So | por |
dc.subject.cnpq | CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | por |
dc.ufscar.embargo | Online | por |
dc.publisher.address | Câmpus Sorocaba | por |
dc.contributor.authorlattes | http://lattes.cnpq.br/2157434731256503 | por |