COLORAÇÃO ACÍCLICA EM GRAFOS PLANARES

Autores

  • Ana Beatriz da Silveira Martins
  • Julio Cesar Silva Araujo

Resumo

Um grafo G é uma tripla ordenada consistindo de um conjunto de vértices (V(G)), um conjunto de arestas (E(G)), e uma relação que associa a cada aresta dois vértices (não necessariamente distintos), chamados de extremidades. Contudo, não trabalharemos aqui com laço (aresta com a mesma extremidade) ou com arestas múltiplas (arestas que tem o mesmo par de extremidades). Desta forma, trataremos apenas de grafos simples. Neste trabalho, estudamos uma variação do problema de Coloração de grafos. Uma k-coloração em vértices de um grafo G é uma atribuição de características (cores) f: V(G) → S tal que |S| = k. Uma k-coloração é dita própria se vértices adjacentes tem cores distintas. O número cromático de um grafo G é o menor inteiro positivo k tal que G admite uma k-coloração própria. O estudo de colorações próprias de um grafo possui diversas aplicações práticas normalmente associadas a problemas de atribuição. Um dos resultados mais famosos em Teoria dos Grafos é que todo grafo planar, ou seja, todo grafo que pode ser representado no plano sem cruzamento de arestas, admite uma 4-coloração própria. Neste trabalho, estudamos generalizações desse conceito de colorações próprias em grafos planares. Uma k-coloração dos vértices em um grafo G é nomeada acíclica se esta não induz qualquer ciclo bicolorido. Estabeleceremos que uma ( k1, k2, ..., kS)-coloração em G é parcialmente acíclica quando suas cores podem ser particionadas em S conjuntos disjuntos (H1, H2, ...HS) com k1, k2, ..., kS cores tais que todo Hi, com 1 ≤ i ≤ S, é aciclicamente colorível. Neste trabalho, estudamos os primeiros artigos no tema de Colorações Acíclicas, que demonstram que Todo grafo planar é aciclicamente 9-colorível e (2,3)-colorível.

Publicado

2019-01-01

Edição

Seção

XXXVIII Encontro de Iniciação Científica