Aspectos gerais sobre a conformabilidade de grafos

• Ano de defesa: 2023
• Autor(a) principal: Alves Junior, Mauro Nigro
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade do Estado do Rio de Janeiro; Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística; Brasil; UERJ; Programa de Pós-Graduação em Ciências Computacionais
• Palavras-chave em Português: Conformable coloring; Total coloring; Computational complexity; Teoria dos grafos; Complexidade computacional; Coloração conformável; Coloração total; CIENCIAS EXATAS E DA TERRA::MATEMATICA::MATEMATICA APLICADA
• Link de acesso: http://www.bdtd.uerj.br/handle/1/20805

Uma k-coloração de vértices de um grafo G = (V,E) é uma atribuição de k cores aos vértices de G, tal que vértices adjacentes têm cores diferentes. A deficiência de G é def(G) = P v∈V (Δ−d(v)). Um grafo G é conformável se G possui uma (Δ+1)-coloração de vértices φ em que o número de classes de cor (incluindo classes de cor vazias) com paridade diferente da paridade de |V | é no máximo def(G). Nesse caso, φ é chamada de coloração conformável. O estudo sobre a coloração conformável abordado nesta tese foi motivado pela rica literatura existente e, principalmente, pelas lacunas envolvendo a determinação da complexidade computacional de decidir se um grafo G é conformável. Uma outra motivação está nas relações inerentes da coloração conformável com o problema de coloração total. Nesta tese, classificamos a conformabilidade para diversas classes de grafos. Determinamos quais colorações equilibradas são conformáveis. Provamos que se G é regular e Classe 1, então L(G) é conformável. Além disso, demonstramos que todo grafo linha do grafo completo Kn é conformável. Ademais, classificamos a conformabilidade dos grafos bipartidos regulares conexos e de todos os grafos subcúbicos, considerando também o caso não-conexo. Para tal, introduzimos uma nova (Δ+1)-coloração de vértices chamada de coloração anticonformável que auxilia em determinar se um grafo é ou não é conformável. Também definimos a coloração conformável forte que é a coloração conformável que se estende para uma (Δ + 1)-coloração total. Mostramos três condições necessárias para uma coloração conformável ser forte e que determiná-la é NP-completo. Abordamos a coloração conformável na união disjunta de grafos. Mostramos um padrão nas uniões disjuntas entre grafos conformáveis, entre grafos anticonformáveis e também entre grafos conformáveis e anticonformáveis. Demonstramos que todo grafo k-regular com k par é não-anticonformável. No caso em que k é ímpar, mostramos que os grafos bipartidos k-regulares são anticonformáveis. Além disso, construímos um grafo não-anticonformável k-regular, denotado por Hk. Finalmente, mostramos que a união disjunta entre Hk e um número ímpar de componentes conexas de Kk+1 é não-conformável.