Colorações distintas nos vértices adjacentes em potências de caminho
Two elements of a graph are adjacent if they are the vertices of an edge, or if they are two edges which share a common vertex, or if they are an edge and one of its vertices. A coloring of a graph is an assignment of colors to its elements (vertices, or edges, or both). Given a colored graph, the...
| Autor principal: | Omai, Mayara Midori |
|---|---|
| Formato: | Dissertação |
| Idioma: | Português |
| Publicado em: |
Universidade Tecnológica Federal do Paraná
2019
|
| Assuntos: | |
| Acesso em linha: |
http://repositorio.utfpr.edu.br/jspui/handle/1/3804 |
| Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
| id |
riut-1-3804 |
|---|---|
| recordtype |
dspace |
| spelling |
riut-1-38042019-02-09T05:01:05Z Colorações distintas nos vértices adjacentes em potências de caminho Adjacent vertex distinguishing colorings on powers of paths Omai, Mayara Midori Almeida, Sheila Morais de http://lattes.cnpq.br/9151881548763857 Nobrega, Diana Sasaki http://lattes.cnpq.br/3041110572471417 Guedes, André Luiz Pires Machado, Raphael Carlos Santos Carmo, Renato José da Silva Almeida, Sheila Morais de Teoria dos grafos Representações dos grafos Computação Cores - Análise Graph theory Representations of graphs Computer science CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Ciência da Computação Two elements of a graph are adjacent if they are the vertices of an edge, or if they are two edges which share a common vertex, or if they are an edge and one of its vertices. A coloring of a graph is an assignment of colors to its elements (vertices, or edges, or both). Given a colored graph, the set of colors of a vertex 𝑣, denoted by 𝐶(𝑣) is composed by the color of 𝑣 and the colors of the edges incident to 𝑣. The Adjacent Vertex Distinguishing Edge Coloring Problem is to find out an edge coloring using the minimum number of colors, such that any two adjacent edges have distinct colors and for each edge 𝑢𝑣, 𝐶(𝑢) ̸= 𝐶(𝑣). The Adjacent Vertex Distinguishing Total Coloring Problem is to find out a total coloring using the minimum number of colors such that any two adjacent elements have distinct colors and for each edge 𝑢𝑣, 𝐶(𝑢) ̸= 𝐶(𝑣). This work presents the solution of the adjacent vertex distinguishing edge coloring problem and the adjacent vertex distinguishing total coloring problem when restricted to the class of the powers of paths. Em um grafo, dois elementos são adjacentes se são um par de vértices que constituem uma aresta, ou se são duas arestas que contêm um mesmo vértice, ou se são uma aresta e um dos vértices que a compõem. Uma coloração de um grafo consiste na atribuição de cores para seus elementos (vértices, ou arestas, ou vértices e arestas). Dado um grafo colorido, o conjunto de cores de um vértice 𝑣, denotado por 𝐶(𝑣), é composto pelas cores das arestas incidentes em 𝑣 e do próprio 𝑣 quando colorido. O Problema da Coloração de Arestas Distinta nos Vértices Adjacentes consiste em apresentar uma coloração de arestas utilizando o menor número de cores de forma que arestas adjacentes tenham cores distintas e para toda aresta 𝑢𝑣, 𝐶(𝑢) ̸= 𝐶(𝑣). O Problema da Coloração Total Distinta nos Vértices Adjacentes consiste em apresentar uma coloração total utilizando o menor número de cores de forma que elementos adjacentes tenham cores distintas e para toda aresta 𝑢𝑣, 𝐶(𝑢) ̸= 𝐶(𝑣). Nesta dissertação apresentamos a solução do problema da coloração de arestas distinta nos vértices adjacentes e do problema da coloração total distinta nos vértices adjacentes quando restritos às potências de caminho. 2019-02-08T12:02:19Z 2019-02-08T12:02:19Z 2018-09-03 masterThesis OMAI, Mayara Midori. Colorações distintas nos vértices adjacentes em potências de caminho. 2018. 84 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2018. http://repositorio.utfpr.edu.br/jspui/handle/1/3804 por openAccess application/pdf Universidade Tecnológica Federal do Paraná Ponta Grossa Brasil Programa de Pós-Graduação em Ciência da Computação Brasil |
| institution |
Universidade Tecnológica Federal do Paraná |
| collection |
RIUT |
| language |
Português |
| topic |
Teoria dos grafos Representações dos grafos Computação Cores - Análise Graph theory Representations of graphs Computer science CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Ciência da Computação |
| spellingShingle |
Teoria dos grafos Representações dos grafos Computação Cores - Análise Graph theory Representations of graphs Computer science CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Ciência da Computação Omai, Mayara Midori Colorações distintas nos vértices adjacentes em potências de caminho |
| description |
Two elements of a graph are adjacent if they are the vertices of an edge, or if they are two edges
which share a common vertex, or if they are an edge and one of its vertices. A coloring of a graph is an assignment of colors to its elements (vertices, or edges, or both). Given a colored graph, the set of colors of a vertex 𝑣, denoted by 𝐶(𝑣) is composed by the color of 𝑣 and the colors of the edges incident to 𝑣. The Adjacent Vertex Distinguishing Edge Coloring Problem is to find out an edge coloring using the minimum number of colors, such that any two adjacent edges have distinct colors and for each edge 𝑢𝑣, 𝐶(𝑢) ̸= 𝐶(𝑣). The Adjacent Vertex Distinguishing Total Coloring Problem is to find out a total coloring using the minimum number of colors such that any two adjacent elements have distinct colors and for each edge 𝑢𝑣, 𝐶(𝑢) ̸= 𝐶(𝑣). This work presents the solution of the adjacent vertex distinguishing edge coloring problem and the adjacent vertex distinguishing total coloring problem when restricted to the class of the powers of paths. |
| format |
Dissertação |
| author |
Omai, Mayara Midori |
| author_sort |
Omai, Mayara Midori |
| title |
Colorações distintas nos vértices adjacentes em potências de caminho |
| title_short |
Colorações distintas nos vértices adjacentes em potências de caminho |
| title_full |
Colorações distintas nos vértices adjacentes em potências de caminho |
| title_fullStr |
Colorações distintas nos vértices adjacentes em potências de caminho |
| title_full_unstemmed |
Colorações distintas nos vértices adjacentes em potências de caminho |
| title_sort |
colorações distintas nos vértices adjacentes em potências de caminho |
| publisher |
Universidade Tecnológica Federal do Paraná |
| publishDate |
2019 |
| citation |
OMAI, Mayara Midori. Colorações distintas nos vértices adjacentes em potências de caminho. 2018. 84 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2018. |
| url |
http://repositorio.utfpr.edu.br/jspui/handle/1/3804 |
| _version_ |
1805324898298494976 |
| score |
10,814766 |