ATA – 14/10/2002

- Polinômio Cromático:

É um polinômio que expressa o número de maneiras de se colorir um grafo com K cores, onde as K cores não precisam ser todas utilizadas na coloração. O poliômio cromático de K_n é dado pela expressão abaixo:

Em qualquer polinômio cromático, para K não negativo, o valor resultante é também não negativo.

- Recorrência: (Teorema 5.3.6)

Se G é um grafo simples e e pertence a E(G), então .

- Teorema 5.3.8

O polinômio cromático possui grau n(G), com coeficientes inteiros alternando em sinal e iniciando em: 1, -e(G), ...

Ou seja, o primeiro coeficiente é 1 o segundo o número de arestas, a partir do terceiro fica difícil determinar.

- Corda:

Uma corda de um ciclo C é uma aresta que não está em C, mas os pontos finais estão em C.

- Ciclo sem Corda:

Um ciclo sem corda é um ciclo de tamanho no mínimo 4 em G que não tem corda, isto é, o ciclo é um sub-grafo induzido de G.

- Grafo cordal:

Um grafo é cordal se ele é simples e não possui um ciclo sem cordas.

Exemplo:

- Vértice Simplicial:

Um vértice é simplicial, se todos os vértices de sua vizinhança, aberta ou fechada, induzem uma clique no grafo original.

Exemplo: (cuidado! no segundo exemplo o vértice apontado não é simplicial)

- Eliminação Perfeita:

É uma ordenação v₁, ..., v_n para remoção de vértices, tal que cada vértice v_i é um vértice simplicial do grafo remanescente.

Exemplo:

Eliminação: 1, 2, 3, 4, 5, 6.

OBS: Se é possível fazer uma eliminação perfeita em um grafo, então ele é cordal e vice-versa.

- Grafo Perfeito:

Um grafo é perfeito, se e somente se, o seu complemento é perfeito.

- Orientação Acíclica:

É uma orientação de um grafo simples G sem ciclos orientados. Fazendo = -1 em , obtém-se o número de orientações acíclicas de G.