Coloração total e coloração total equilibrada de Famílias de Snarks

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorSouza, Simone Dantas de-
Autor(es): dc.contributorNobrega, Diana Sasaki-
Autor(es): dc.creatorAlmeida, Luana Cordeiro de-
Data de aceite: dc.date.accessioned2024-07-11T17:39:37Z-
Data de disponibilização: dc.date.available2024-07-11T17:39:37Z-
Data de envio: dc.date.issued2019-04-08-
Data de envio: dc.date.issued2019-04-08-
Data de envio: dc.date.issued2017-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/9128-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/754845-
Descrição: dc.descriptionUm grafo cúbico é dito Tipo 1 se admite uma coloração total com 4 cores. Em caso contrário, é possível encontrar uma coloração total desse grafo com 5 cores e ele é dito Tipo 2. Em 2003, Cavicchioli, Murgolo, Ruini e Spaggiari apresentaram um abrangente estudo sobre classes especiais de grafos e reportam que todos os snarks livres de quadrado e ciclicamente 4-aresta-conexos com até 30 vértices são Tipo 1. Esse achado os levou a propor o problema de achar o menor desses snarks Tipo 2. Uma questão relacionada a essa é a de coloração total equilibrada, isto é, em que a diferença entre o número de vezes que cada cor é usada é de, no máximo, 1. Grafos cúbicos sempre admitem colorações totais equilibradas com 4 ou 5 cores mas esse problema de classificação é NP-completo, como mostrado por Dantas et al. em 2016,e nesse mesmo artigo os autores propuseram o problema de encontrar um grafo cúbico Tipo 1 com cintura maior que 4 e número de coloração total equilibrada 5. Procurando contribuir com essas investigações, em nosso trabalho apresentamos colorações totais equilibradas utilizando 4 cores para a primeira família de snarks de Loupekine e a estendemos para colorações totais equilibradas com 4 cores de produtos internos entre snarks dessa família e das famílias de Goldberg, Flor e para colorações totais de produtos entre snarks de Loupekine e de Blanusa. Também utilizamos o produto interno para obter uma nova família infinita de snarks Tipo 2-
Descrição: dc.descriptionA cubic graph is said to be Type 1 if it admits a total colouring with 4 colours. Otherwise, it is possible to find for this graph a total colouring with 5 colours and it is said to be Type 2. In 2003, Cavicchioli, Murgolo, Ruini and Spaggiari presented a comprehensive study on special classes of graphs in which they reported all squarefree cyclically 4-edge-connected snarks with at most 30 vertices are Type 1. This lead them to question what is the smallest Type 2 snark with these properties. A related question to this one is to find an equitable total colouring, i.e., a total colouring for which the cardinalities of colour classes differ by at most 1. Cubic graphs always admit an equitable total colouring with 4 or 5 colours but classifying them is a NP-Complete problem, as shown by Dantas et al. in 2016. In the same paper, the authors posed the problem of finding a cubic Type 1 graph with girth at least 5 that does not admit an equitable total colouring with 4 colours. Our goal in this work is to contribute to answer these questions. We present equitable total colourings for the first family of Louekine snarks and extend these colourings for dot products between Loupekine and Flower, Goldberg or Blanuˇsa snarks. We also use dot product to find a new infinite family of Type 2 snarks-
Descrição: dc.description67 f.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsopenAccess-
Direitos: dc.rightsopenAccess-
Direitos: dc.rightshttp://creativecommons.org/licenses/by-nc-nd/3.0/br/-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectGrafos-
Palavras-chave: dc.subjectsnarks-
Palavras-chave: dc.subjectColoração total-
Palavras-chave: dc.subjectColoração total equilibrada-
Palavras-chave: dc.subjectTeoria dos grafos-
Palavras-chave: dc.subjectGraph theory-
Palavras-chave: dc.subjectSnarks-
Palavras-chave: dc.subjectTotal coloring-
Palavras-chave: dc.subjectEquitable total coloring.-
Título: dc.titleColoração total e coloração total equilibrada de Famílias de Snarks-
Tipo de arquivo: dc.typeDissertação-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.