30 abr 2025
10:00 Defesa de Mestrado Integralmente à distância
Tema
Sobre (2, 1)-colorações em grafos exoplanares
Aluno
Adilson Luis Jönck Júnior
Orientador / Docente
Christiane Neme Campos
Breve resumo
Esta dissertação aborda colorações impróprias, uma extensão da área clássica de coloração de grafos, com ênfase em (2,1)-colorações aplicadas a grafos exoplanares. Grafos exoplanares são grafos planares que admitem uma imersão no plano de maneira que todos os seus vértices estejam localizados na fronteira da face externa. Colorações impróprias generalizam colorações próprias, permitindo que vértices adjacentes recebam a mesma cor, mas sob certas restrições. Em particular, nas (2,1)-colorações, são atribuídas duas cores aos vértices, e cada vértice pode ter, no máximo, um vizinho com a mesma cor que a ele foi atribuída.
Inicialmente são introduzidos conceitos clássicos e a notação básica da Teoria de Grafos. Em seguida, são apresentadas definições e resultados relevantes para o contexto da pesquisa desenvolvida neste trabalho. Em particular, são estabelecidas propriedades estruturais de grafos exoplanares e variantes de colorações impróprias. Um histórico da pesquisa existente na área estudada também é apresentado.
Os resultados obtidos nesta pesquisa são apresentados no Capítulo 3. Foi demonstrado que grafos exoplanos com no máximo três faces triangulares admitem (2,1)-colorações. Além disso, foram apresentadas famílias de grafos exoplanos com mais de três faces triangulares que admitem e outras que não admitem (2,1)-colorações, evidenciando que o limite encontrado é justo. Para os grafos exoplanares maximais, os resultados obtidos são mais definitivos: foram estabelecidas condições necessárias e suficientes para que esses grafos admitam (2,1)-colorações.
Banca examinadora
Titulares:
| Christiane Neme Campos | IC/UNICAMP |
| Lehilton Lelis Chaves Pedrosa | IC/UNICAMP |
| Claudia Linhares Sales | DC/UFC |
Suplentes:
| João Meidanis | IC/UNICAMP |
| Sheila Morais de Almeida | UTFPR |