Os números de capítulos, seções, teoremas e exercícios se referem ao livro de Diestel, 2-a edição.

5. Coloring

Uma k-coloração dos vértices de um grafo G é uma função c de V(G) em {1, … , k} tal que c(v) é diferente de c(w) sempre que v e w forem adjacentes.
Em outras palavras, uma k-coloração dos vértices é uma partição de V(G) em conjuntos independentes.
O número cromático (= chromatic number) de G é o menor k tal que G admite uma k-coloração dos vértices. Notação: chi(G).

Exercícios:
1. Suponha que chi(G) = k. Se e é uma aresta, quanto vale chi(G−e)? Se v é um vértice, quanto vale chi(G−v)?
2. Suponha que chi(G) ≥ k. É verdade que chi(H) = k para algum subgrafo H de G?

5.1 Coloração de grafos planares

Teorema 5.1.1 (das 4 cores): Todo grafo planar admite uma 4-coloração dos vértices.
A demonstração do teorema das 4 cores é muito difícil. Mas é fácil provar a seguinte Proposição 5.1.2 (teorema das 5 cores, Heawood): Todo grafo planar admite uma 5-coloração dos vértices.
Todo grafo plano admite uma 4-coloração das faces.

5.2 Coloração de vértices

O número de coloração (= coloring number) é o menor k para o qual G admite uma enumeração dos vértices tal que cada vértice é precedido por menos que k de seus vizinhos. [Cuidado! Definição delicada.] Notação: col(G).
Fato: chi(G) ≤ col(G).
Fato: col(G) ≤ Delta(G) + 1.
Proposição 5.2.2: col(G) = max delta(H) + 1, onde max é tomado sobre todos os subgrafos H de G.
Corolário 5.2.3: Todo grafo G tem um subgrafo H com delta(H) ≥ chi(G) − 1.
Um valor elevado de chi(G) não está relacionado com valores elevados de delta(G) ou kappa(G). Mas um valor elevado de chi(G) implica em valor elevado de delta(H) e kappa(H) para algum subgrafo H de G (a recíproca não é verdadeira). [Veja cap.8.]
O parâmetro chi é global: existem grafos com chi elevado que localmente parecem florestas e portanto podem ser coloridos com 2 cores apenas (veja Teorema 11.2.2).
A classe dos grafos k-construtíveis (= k-constructible) é definida recursivamente:
1. K^k é k-construtível;
2. se G é k-construtível e x,y é um par de vértices não adjacentes então (G+xy) / xy é k-construtível;
3. se G₁ e G₂ são k-construtíveis e existem vértices x, y₁ e y₂ tais que x é o único vértice comum dos dois grafos e xy₁ e xy₂ são arestas de G₁ e G₂ respectivamente então (G₁ ∪ G₂) − xy₁ − xy₂ + y₁y₂ é k-construtível.
Aqui, / xy denota a contração da aresta xy.
Não é verdade que chi(G) ≥ k garante que G contém K^k. Entretanto …
Teorema 5.2.5 (Hajós): chi(G) ≥ k se e só se G tem um subgrafo k-construtível.
(Urquhart mostrou que é possível trocar tem um subgrafo por é).

Exercícios:
1. Suponha que chi(G) ≥ k. Mostre que G tem um subgrafo H tal que delta(H) ≥ k−1. Mostre que G tem um subgrafo J tal que kappa(J) ≥ ⌊(k−1)/4⌋.
2. [5.9] Seja psi(G) a arboricidade de G, ou seja, o menor número de florestas cuja união é igual a G. Encontre uma função f tal que todo grafo G com psi(G) ≥ f (k) tem col(G) ≥ k. Encontre uma função g tal que todo grafo G com col(G) ≥ g(k) tem psi(G) ≥ k.
3. Suponha que G tem uma orientação acíclica tal que o grau de saída de cada vértice é menor que k. Mostre que o grafo admite uma k-coloração.
4. Mostre que chi(G) ≥ |G| / alpha(G).
5. [5.13] Para cada k, encontre uma constante c_k tal que todo grafo G com |G| ≥ 3k e alpha(G) ≤ k tem um ciclo de comprimento ≥ c_k|G|.
6. Suponha que H é k-construtível. Quanto vale chi(H)?
7. Suponha que H é um grafo minimal com relação à propriedade chi(H) = k. É verdade que H é k-construtível?
8. [5.22, difícil] Para cada k, construa um grafo G sem triângulos tal que chi(G) = k.

5.3 Coloração de arestas

Uma k-coloração das arestas de um grafo G é uma função c de E(G) em {1, … , k} tal que c(e) é diferente de c(f) sempre que e e f forem adjacentes (ou seja, tiverem uma ponta em comum).
Em outras palavras, uma k-coloração das arestas é uma partição de E(G) em emparelhamentos.
O índice cromático (= chromatic index = edge-chromatic number) de G é o menor k tal que G admite uma k-coloração das arestas. Notação: chi'(G).
Proposição 5.3.1 (König): Se G é bipartido então chi'(G) = Delta(G).
Teorema 5.3.2 (Vizing): Para todo grafo G, Delta(G) ≤ chi'(G) ≤ Delta(G) + 1.
(Na versão para multigrafos, é preciso levar em conta a multiplicidade das arestas.)

5.4 List coloring

Uma lista de cores é um conjunto de números naturais. Para cada vértice v de G, seja S_v uma lista de cores. Diremos que S é uma família de listas de cores.
Uma coloração dos vértices de G a partir de uma família S de listas de cores é uma função c que associa um número natural a cada vértice de tal modo que
1. c(v) esteja em S_v para cada v e
2. c(v) seja diferente de c(w) sempre que v e w forem adjacentes.
G é k-choosable se admite uma coloração a partir de qualquer família S de listas de cores tal que |S_v| = k para cada vértice v.
O choice number de G é o menor k para o qual G é k-choosable. Notação: ch(G). É evidente que ch(G) ≥ chi(G).
Teorema 5.4.2 (Thomassen): Todo grafo planar é 5-choosable (isto é, se G é planar então ch(G) ≤ 5).

Exercícios:
1. Suponha que um vértice u de um grafo G tem três vizinhos: x, y e z. Associe uma lista de cores permitidas a cada vértice de G−u: as listas associadas a x, y e z são 2, … , k e as listas associadas aos demais vértices são 1,2, … , k. Mostre que G admite uma k-coloração ordinária se e só se G−u admite uma coloração a partir das listas.
2. Mostre que ch(K_3,3) > 2.
3. [5.24] Para todo k, encontre um grafo G tal que chi(G) = 2 e ch(G) ≥ k.
4. Encontre um grafo planar G tal que ch(G) > 4.
5. [5.23] Mostre que ch(G) ≤ 6 para todo grafo planar G. Não use o Teorema 5.4.2.
6. Suponha que G tem uma orientação acíclica tal que o grau de saída de cada vértice v é menor que |S_v|. Mostre que o grafo admite uma coloração a partir das listas S.

5.4′ List edge-coloring

ch'(G) é definido por analogia com ch(G). (Se preferir, ch'(G) := ch(L(G)), sendo L(G) o grafo-das-arestas de G)
Conjectura: ch'(G) = chi'(G).
Teorema 5.4.4 (Galvin): Se G é bipartido então ch'(G) = chi'(G).

Exercícios:
1. [5.25] Encontre uma delimitação superior geral de ch'(G) em termos de chi'(G).
2. Um núcleo (= kernel) de um grafo orientado é um conjunto independente U tal que, para todo vértice v fora de U, existe uma aresta de v para U. (O conceito de núcleo é usado na prova do Teorema 5.4.4.) Suponha que D é um grafo orientado e que todo subgrafo induzido de D tem um núcleo. D pode ter ciclos orientados pares? ímpares?
3. [5.29] Encontre um grafo orientado que não tenha núcleo.
4. [Mário Leston] Mostre que todo grafo orientado acíclico tem um núcleo. (Portanto, todo subgrafo de um grafo orientado acíclico também tem um núcleo.)
5. Que grafos orientados têm núcleo? Como encontrar o núcleo de um grafo orientado? Que grafos orientados gozam da propriedade de que qualquer um de seus subgrafos tem um núcleo? É verdade que toda orientação de um grafo-das-arestas (=line graph) tem um núcleo?
6. [5.30, difícil] (Teorema de Richardson) Mostre que todo grafo orientado sem ciclos orientados de comprimento ímpar tem um núcleo.
7. Faça uma ilustração do teorema de Galvin. Comece com uma coloração das arestas de K_3,3 − M, onde M é um emparelhamento. Construa o correspondente grafo orientado. Mostre núcleos de alguns de seus subgrafos induzidos.
8. Mostre que a orientação do grafo L(G) definida na demonstração do teorema de Galvin não é necessariamente acíclica. Mostre que existe um grafo bipartido G que não admite uma orientação acíclica tal que o grau de saída de cada vértice é menor que Delta(G).

5.5 Grafos perfeitos

Veja sítio de Vasek Chvátal sobre grafos perfeitos: problems, papers, people.

O livro de Jensen e Toft é uma referência obrigatória sobre coloração de vértices e arestas.