CONJECTURA DE HOFFMANN-OSTENHOF

XXXVII Encontro de Iniciação Científica

Isnard Lopes Costa, Victor Almeida Campos

A 3-Decomposition Conjecture (3DC) estabelece que cada grafo conexo cúbico pode ser decomposto em uma árvore geradora, um subgrafo 2-regular e um emparelhamento. Estudamos o artigo &quot;Decomposing planar cubic graphs&quot; de Arthur Hoffmann-Ostenhof, Tomás Kaiser e Kenta Ozeki o qual mostra que esta conjectura é verdadeira para a classes dos grafos cúbicos planares conexos. Todos os grafos considerados são finitos e sem laços. Uma decomposição de um grafo G é um conjunto de subgrafos cujos conjuntos de arestas particionam o conjunto das arestas de G. Qualquer um desses subgrafos pode ser o grafo vazio - isto é, um grafo cujo conjuto de vértices é vazio - a menos que seja excluídos por restrições adicionais (tais como ser uma árvore geradora). Consideramos emparelhamentos em decomposições como subgrafos 1-regular. O subgrafo 2-regular, na 3DC pode ser vazio, enquanto que o emparelhamento não. A 3DC foi provada para grafos cúbicos planares e planares-projetivos 3-conexo em arestas em &quot;K. Ozeki, D. Ye, Decomposing plane cubic graphs, European J. Combin. 52 (2016), 40–46&quot;. Também é conhecido que essa conjectura é válida para grafos cúbicos Hamiltonianos. Chamamos um ciclo C em um grafo conexo de separador se G − E(C) é desconexo. Foi mostrado que 3DC é equivalente a seguinte conjecture, chamada 2-Decomposition Conjecture (2DC). 2DC: Seja G um grafo conexo com vértices de grau dois e três, apenas, tal que todo ciclo de G é separador. Então G pode ser decomposto em uma árvore geradora e um emparelhamento não-vazio. O objetivo da bolsa foi estudar e entender o artigo visando resolver a conjectura para o caso geral.

Palavras-chave: grafo cúbico. grafo 3-regular. decomposição. árvore geradora.

Encontros Universitários da UFC, Fortaleza, v. 3, 2018

1165