Coloracão arco-íris em classes de grafos

• Ano de defesa: 2020
• Autor(a) principal: Rocha, Aleffer
• Orientador(a): Almeida, Sheila Morais de
• Banca de defesa: Luiz, Atílio Gomes , Groshaus, Marina Esther , Carmo, Renato José da Silva , Almeida, Sheila Morais de
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Tecnológica Federal do Paraná; Ponta Grossa
• Programa de Pós-Graduação: Programa de Pós-Graduação em Ciência da Computação
• País: Brasil
• Palavras-chave em Português: Teoria dos grafos; Arco-íris; Conectividade (Computadores); Graph theory; Rainbow; Connection machines
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.utfpr.edu.br/jspui/handle/1/5232

Problemas de coloração arco-íris, com notáveis aplicações em segurança de informação, têm recebido bastante atenção nos últimos anos na área de Combinatória. Em particular, o número de conexão arco-íris de um grafo conexo , denotado por (), é o menor inteiro para o qual admite uma -coloração de arestas (não necessariamente própria) tal que, entre qualquer par de vértices, existe um caminho arco-íris, ou seja, um caminho em que as cores das arestas são todas distintas. Dada uma coloração de arestas para um grafo , se entre cada par de vértices existe um caminho mínimo que é arco-íris, então é uma coloração arco-íris forte. O menor número de cores que permite uma coloração arco-íris forte de um dado grafo é o número de conexão arco-íris forte de . Um grafo é arco-íris crítico se a remoção de uma aresta qualquer aumenta o número de conexão arco-íris de . Neste trabalho, são determinados o número de conexão arco-íris e o número de conexão arco-íris forte dos grafos sombras de caminhos, cobras triangulares triplas, circulantes 1, 2 e junção + quando tem () ≤ 2. Também foram determinados os números de conexão arco-íris dos grafos junção de sunlet () com quando | ()| ≥ − 1 e de cografos com três vértices pendentes. Foram encontrados novos limitantes superiores para o número de conexão arco-íris dos grafos cobras, de junção de dois grafos com vértice universal e de junção + quando ≤ −2. Também são apresentadas condições necessárias e suficientes para a criticalidade dos grafos leque, dos produtos cartesianos de × quando () = () ≥ 2 ou quando é uma panela, × quando () = () ≥ 1 e de × , quando e são pares.