grafos:listcolouring [WikiMat]

Aqui daremos uma olhada em uma generalização relativamente recente dos conceitos de coloração. Essa generalização pode parecer um pouco exagerada à primeira vista, mas acaba fornecendo uma ligação fundamental entre os números cromáticos clássicos (vértice e aresta) de um grafo e seus outros invariantes.

Suponha que nos seja dado um grafo $G=(V,E)$, e para cada vértice de $G$ uma lista de cores permitidas no vértice particular: quando podemos colorir $G$ (no sentido usual) de modo que cada vértice receba uma cor de sua lista? Mais formalmente, seja $(S_v)_{v \in V}$ uma família de conjuntos. Chamamos uma coloração de vértice $\mathcal{c}$ de $G$ com $\mathcal{c}(v) \in S_v$ para todo $v \in V$ uma coloração das listas $S_v$. O grafo $G$ é chamado $k$-lista-colorível , ou $k$-escolhível , se, para cada família $(S_v)_{v \in V}$ com $|S| = k$ para todo $v$, existe uma coloração de vértice de $G$ das listas $S_v$. O menor inteiro $k$ para o qual $G$ é $k$-escolhível é o número cromático da lista, ou número de escolha $ch(G)$ de $G$.

Colorações de lista de arestas são definidas de forma análoga. o menor inteiro $k$ tal que $G$ tem uma coloração de aresta de qualquer família de listas de tamanho $k$ é o índice cromático da lista $ch'(G)$ de $G$; formalmente, apenas definimos $ch'(G) := ch(L(G))$, onde $L(G)$ é o grafo de linha de $G$.

Em princípio, mostrar que um dado grafo é $k$-escolhível é mais difícil do que provar que ele é $k$-colorível: o último é apenas o caso especial do primeiro, onde todas as listas são iguais a $\{1, \dots ,k\}$. Assim,

$$ch(G) \geq \chi(G)$$ e $$ch'(G) \geq \chi '(G)$$

para todos os grafos $G$.

Apesar dessas desigualdades, muitos dos limites superiores conhecidos para o número cromático mostraram-se válidos também para o número de escolha. Exemplos desse fenômeno incluem o Teorema de Brooks e a Proposição; em particular, grafos de grande número de escolha ainda possuem subgrafos de grande grau mínimo. Por outro lado, é fácil construir grafos para os quais os dois invariantes estão separados. Tomados em conjunto, esses dois fatos indicam um pouco a que distância esses limites superiores gerais do número cromático podem estar da verdade.

O teorema a seguir mostra que, em termos de sua relação com outras invariantes do grafo, o número de escolha difere fundamentalmente do número cromático. Como mencionado anteriormente, existem grafos $2$-cromáticos de grau mínimo arbitrariamente grande, por exemplo, os grafos $K_{n,n}$. O número de escolha, no entanto, será forçado por grandes valores de invariantes como $\delta , \varepsilon$ ou $\kappa$:

Teorema (Alon)

Existe uma função $f: \mathbb{N} \to \mathbb{N}$ tal que, dado qualquer inteiro $k$, todos os grafos $G$ com grau médio $d(G) \geq f(k)$ satisfazem $ch(G) \geq k$.

A prova deste Teorema usa métodos probabilísticos introduzidos mais a frente.

Embora as declarações da forma $ch(G) \leq k$ sejam formalmente mais fortes do que a declaração correspondente de $\chi (G) \leq k$ , elas podem ser mais fáceis de provar. Um belo exemplo é a versão em lista do teorema das cinco cores: “Todo grafo planar pode ser $5$-escolhível.”. A prova disso não usa o teorema das cores físicas (ou mesmo a fórmula de Euler, na qual se baseia a prova do teorema das cinco cores). Assim, reobtemos o teorema das cores como corolário, com uma prova muito diferente.

Teorema (Thomassen)

Todo grafo planar é $5$-escolhível.

Demonstração:

Vamos provar a seguinte afirmação para todos os grafos planos $G$ com pelo menos $3$ vértices:

Suponha que cada face interna de $G$ seja limitada por um triângulo e sua face externa por um ciclo $C = v_1 \dots v_kv_1$. Suponha ainda que $v_1$ já tenha sido colorido com a cor $1$, e $v_2$ tenha sido colorido com $2$. Suponha finalmente que com todos os outros vértices de $C$ uma lista de pelo menos $3$ cores é associada, e a cada vértice de $G-C$ uma lista de pelo menos $5$ cores. Então a coloração de $v_1$ e $v_2$ pode ser estendida para uma coloração de $G$ para as listas dadas. $\qquad (*)$

Verifiquemos primeiro que $(*)$ implica a afirmação do teorema. Seja dado qualquer grafo plano, juntamente com uma lista de $5$ cores para cada vértice. Adicione arestas a este grafo até que seja um grafo plano maximal $G$. Pela Proposição, $G$ é uma triangulação plana; seja $v_1v_2v_3v_1$ o limite de sua face externa. Agora colorimos $v_1$ e $v_2$ (diferentemente) de suas listas e estendemos essa coloração por $(*)$ para uma coloração de $G$ das listas dadas.

Provemos agora $(*)$, por indução em $|G|$. Se $|G|=3$, então $G = C$ e a afirmação é trivial. Agora seja $|G| \geq 4$, e assuma $(*)$ para grafos menores. Se $C$ tem uma corda $vw$, então $vw$ está em dois únicos ciclos $C_1,C_2 \subseteq C+ vw$ com $v_1v_2 \in C_1$ e $v_1v_2 \notin C_2$. Para $i=1,2$, deixe $G_i$ denotar o subgrafo de $G$ induzido pelos vértices situados em $C_i$ ou em sua face interna.

Aplicando a hipótese de indução primeiro a $G_1$ e então, com as cores agora atribuídas a $v$ e $w$, a $G_2$ produz a coloração desejada de $G$.

Se $C$ não tem corda , sejam $v_1,u_1,\dots,u_m,v_{k-1}$ os vizinhos de $v_k$ em sua ordem cíclica natural em torno de $v_k$ (como na primeira prova do teorema das cinco cores); pela definição de $C$, todos os vizinhos $u_i$ estão na face interna de $C$.

Como as faces internas de $C$ são limitadas por triângulos, $P := v_1u_1 \dots u_mv_{k-1}$ é um caminho em $G$, e $C' := P \cup (C-v_k)$ um ciclo.

Agora escolhemos duas cores diferentes $j, \ell \neq 1$ da lista de $v_k$ e excluímos essas cores das listas de todos os vértices $u_i$. Então toda lista de um vértice em $C'$ ainda tem pelo menos $3$ cores, então por indução podemos colorir $C'$ e seu interior , ou seja, o gráfico $G_v_k$. Pelo menos uma das duas cores $j, \ell$ não é usada para $v_{k-1}$, e podemos atribuir essa cor a $v_k$.

Como costuma acontecer com provas por indução, a chave para a prova acima está em seu fortalecimento delicadamente equilibrado da afirmação provada. Em comparação com a coloração comum, a tarefa de encontrar um reforço adequado é muito facilitada pela possibilidade de fornecer diferentes listas de vértices de diferentes comprimentos e, assim, adaptar o problema de coloração de forma mais adequada à estrutura do grafo. Isso sugere que talvez em outros problemas de coloração não resolvidos também seja vantajoso apontar diretamente para a versão da lista, ou seja, provar uma afirmação da forma $ch(G) \leq k$ em vez do formalmente mais fraco $\chi (G) \leq k$. Infelizmente, essa abordagem falha para o teorema das quatro cores: grafos planares não são $4$-escolhíveis em geral.

Como mencionado anteriormente, o número cromático de um grafo e seu número de escolha podem diferir muito. Surpreendentemente, no entanto, nenhum exemplo é conhecido para colorações de arestas. Na verdade, foi conjecturado que nenhum existe:

Conjectura da coloração de lista

Todo grafo $G$ satisfaz $ch'(G) = \chi '(G)$.

Vamos provar a conjectura de coloração de lista para grafos bipartidos. Como ferramenta usaremos orientações de grafos. Se $D$ é um grafo direcionado e $v \in V(D)$, denotamos por $N^+(v)$ o conjunto e por $d^+(v)$ o número de vértices $w$ tais que $D$ contém uma aresta direcionada de $v$ para $w$.

Para ver como as orientações entram em jogo no contexto da coloração, relembre o algoritmo ganancioso. Isso colore os vértices de um grafo $G$ por sua vez, seguindo uma ordenação previamente fixada $(v_1,\dots,v_n)$, com a menor cor disponível. Esta ordenação define uma orientação de $G$ se orientarmos cada aresta $v_iv_j$ 'para trás' , ou seja, de $v_j$ para $v_i$ se $i < j$. Então, para determinar uma cor para $v_j$, o algoritmo apenas olha para os vizinhos previamente coloridos de $v_j$, aqueles para os quais $v_j$ envia uma aresta direcionada. Em particular, se $d^+(v) <k$ para todos os vértices $v$, o algoritmo usará no máximo $k$ cores.

Se reescrevermos a prova desse fato (um tanto desajeitadamente) como uma indução formal em $k$, a propriedade essencial do conjunto $U$ de vértices coloridos $1$ é que todo vértice em $G-U$ envia uma aresta para $U$: isso perdura que $d_{G-U}^+(v) < d_G^+(v)$ para todo $v \in G-U$, então podemos colorir $G-U$ com as $k-1$ cores restantes pela hipótese de indução.

O seguinte lema generaliza essas observações para listar coloração e para orientações $D$ de $G$ que não necessariamente vêm de uma enumeração de vértice, mas podem conter alguns ciclos direcionados. Chamemos um conjunto independente $U \subseteq V(D)$ um núcleo de $D$ se, para cada vértice $v \in D-U$ existe uma aresta em $D$ direcionada de $v$ a um vértice em $U$. Observe que núcleos de grafos direcionados não-vazios são eles próprios não-vazios.

Lema

Seja $H$ um grafo e $(S_v)_{v \in V(H)}$ uma família de listas. Se $H$ tem uma orientação $D$ com $d^+(v) < |S_v|$ para todo $v$, e tal que todo subgrafo induzido de $D$ tem um núcleo, então $H$ pode ser colorido a partir das listas $S_v$.

Demonstração:

Aplicamos indução em $|H|$. Para $|H| = 0$ tomamos a coloração vazia. Para o passo de indução, seja $|H| > 0$. Seja $\alpha$ uma cor que ocorre em uma das listas $S_v$, e seja $D$ uma orientação de $H$ como indicado. Os vértices $v$ com $\alpha \in S_v$ abrangem um subgrafo não-vazio $D'$ em $D$; por suposição, $D'$ tem um núcleo $U \neq \emptyset$.

Vamos colorir os vértices em $U$ com $\alpha$, e remover $\alpha$ das listas de todos os outros vértices de $D'$. Como cada um desses vértices envia uma aresta para $U$, as listas modificadas $S_v'$ para $v \in D-U$ novamente satisfazem a condição $d^+(v) < |S_v'|$ em $D-U$. Como $D-U$ é uma orientação de $H-U$, podemos então colorir $H-U$ dessas listas pela hipótese de indução. Como nenhuma dessas listas contém $\alpha$, isso estende nossa coloração $U \to \{\alpha\}$ para a coloração de lista desejada de $H.$

Em nossa prova da conjectura de coloração de lista para grafos bipartidos, aplicaremos o Lema acima apenas para coloração de listas de comprimento uniforme $k$. No entanto, observe que manter os comprimentos de lista variáveis é essencial para a prova do próprio lema: sua simples indução poderia não ser executada com comprimentos de lista uniformes.

Teorema (Galvin)

Todo grafo bipartido $G$ satisfaz $ch'(G) = \chi '(G)$.

Demonstração:

Seja $G =: (X \cup Y,E)$, onde $\{X,Y\}$ é uma bipartição de vértice de $G$. Dizemos que duas arestas de $G$ se encontram em $X$ se elas compartilham uma extremidade em $X$, e correspondentemente para $Y$. Seja $\chi '(G) =: k$, e seja $\mathcal{c}$ uma $k$-aresta- coloração de $G$ .

Claramente, $ch'(G) \geq k$; provamos que $ch'(G) \leq k$. Nosso plano é usar o Lema acima para mostrar que o grafo de linha $H$ de $G$ é $k$-escolhível. Para aplicar o lema, basta encontrar uma orientação $D$ de $H$ com $d^+(e) < k$ para todo vértice $e$ de $H$, e tal que todo subgrafo induzido de $D$ tenha um núcleo. Para definir $D$, considere $e,e' \in E$ adjacente, digamos com $\mathcal{c}(e) < \mathcal{c}(e')$. Se $e$ e $e'$ se encontram em $X$, orientamos a aresta $ee' \in H$ de $e'$ em direção a $e$; se $e$ e $e'$ se encontram em $Y$, nós o orientamos de $e$ para $e'$.

Vamos calcular $d^+(e)$ para $e \in E = V(D)$ dado. Se $\mathcal{c}(e) = i$, digamos, então todo $e' \in N^+(e)$ que encontra $e$ em $X$ tem sua cor em $\{1,\dots,i-1\}$ e todo $e' \in N^+(e)$ que encontra $e$ em $Y$ tem sua cor em $\{i+1,\dots,k\}$. Como quaisquer dois vizinhos $e'$ de $e$ encontrando $e$ ambos em $X$ ou ambos em $Y$ são adjacentes e, portanto, coloridos de maneira diferente, o que implica em $d^+(e) < k$ como desejado.

Resta mostrar que todo subgrafo induzido $D'$ de $D$ tem um núcleo. Isso, no entanto, é imediato pelo teorema do casamento estável para $G$, se interpretarmos as direções em $D$ como expressando preferência. De fato, dado um vértice $v \in X \cup Y$ e arestas $e,e' \in V(D')$ em $v$, escreva $e <_v e'$ se a aresta $ee'$ de $H$ for direcionada de $e$ para $e'$ em $D$. Então qualquer emaprelhamento estável no grafo $(X \cup Y, V(D'))$ para este conjunto de preferências é um núcleo em $D'$.

Pela Proposição , agora conhecemos o índice lista-cromático exato de grafos bipartidos: