Colorações de arestas distinguidoras em potências de caminhos
A proper edge coloring of a graph 𝐺 is an assignment of colors to the edges of 𝐺 such that edges that share a common vertex receive distinct colors. Give a graph with an edge coloring, the set of colors of a vertex 𝑣 is the set of the colors of the edges incident with 𝑣. A proper edge coloring is an...
| Autor principal: | Salgado, Pedro Henrique |
|---|---|
| Formato: | Trabalho de Conclusão de Curso (Graduação) |
| Idioma: | Português |
| Publicado em: |
Universidade Tecnológica Federal do Paraná
2023
|
| Assuntos: | |
| Acesso em linha: |
http://repositorio.utfpr.edu.br/jspui/handle/1/30627 |
| Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
| Resumo: |
A proper edge coloring of a graph 𝐺 is an assignment of colors to the edges of 𝐺 such that edges that share a common vertex receive distinct colors. Give a graph with an edge coloring, the set of colors of a vertex 𝑣 is the set of the colors of the edges incident with 𝑣. A proper edge coloring is an adjacent-vertex-distinguishing edge coloring if, for any two adjacent vertices, theirs set of colors are distinct; and it is a vertex-distinguishing edge coloring when, for any two (not necessarily adjacent) vertices, its set of colors are distinct. The Adjacent-Vertex-Distinguishing Edge Coloring Problem is to determine the minimum number of colors for an adjacent-vertex-distinguishing edge coloring of a given graph 𝐺. This number is called the adjacent-vertex-distinguishing chromatic index. Similarly, the Vertex-Distinguishing Edge Coloring Problem is to determine the minimum number of colors for a vertex-distinguishing edge coloring of a given graph 𝐺. This number is called the vertex-distinguishing chromatic index. The 𝑘-th power of a path with 𝑛 vertices is the graph obtained from the path with 𝑛 vertices by adding edges between any two vertices at distance at most 𝑘. Omai et al. determined the adjacent-vertex-distinguishing chromatic index of the powers of paths. To that end, the problem was divide into cases that used several different edge coloring techniques. We present a new technique to obtain an adjacent-vertex-distinguishing edge coloring of powers of paths which contain universal vertices. This new technique is applicable to cases that were previously treated separately, being a simpler proof. Moreover, this technique allows to determine the vertex-distinguishing chromatic index of a subset of powers of paths with universal vertex. |
|---|