Razões pelas quais um gráfico pode não ser colorido?

21

Ao raciocinar um pouco sobre essa questão , tentei identificar todas as diferentes razões pelas quais um gráfico pode não ser colorido. Estas são as únicas duas razões que eu consegui identificar até agora:kG=(VG,EG)k

  1. G contém uma camarilha do tamanho . Esta é a razão óbvia.k+1
  2. Existe um subgrafo de modo que as duas afirmações a seguir são verdadeiras:GH=(VH,EH)G

    • H não é colorável.k1
    • xVGVH yVH {x,y}EG . Em outras palavras, existe um nó em , mas não em , de tal modo que está ligado a cada nó em .G H x HxGHxH

Podemos ver as duas razões acima como regras. Ao aplicá-los recursivamente, as duas únicas maneiras de criar um gráfico não colorável que não contém um clique são:k + 1kk+1

  1. Comece com um ciclo de comprimento uniforme (que é cores) e aplique a regra 2 por vezes. Observe que uma aresta não é considerada um ciclo de comprimento (caso contrário, esse processo teria o efeito de criar uma camarilha ).k - 1 2 k + 12k12k+1
  2. Comece com um ciclo de comprimento ímpar (que é de cores) e aplique a regra 2 por vezes. A duração do ciclo inicial deve ser maior que (caso contrário, esse processo teria o efeito de criar uma camarilha ).k - 2 3 k + 13k23k+1

Questão

Existe algum outro motivo, além daqueles 2 acima, que torna um gráfico não colorido?k

 
Update 30/11/2012

Mais precisamente, o que eu preciso é de algum teorema da forma:

Um gráfico tem o número cromático se e somente se ...χ ( G ) = k + 1Gχ(G)=k+1

O cálculo de Hajós , apontado por Yuval Filmus em sua resposta, é um exemplo perfeito do que estou procurando, pois um gráfico tem o número cromático se e somente se puder ser derivado do axioma aplicando repetidamente as 2 regras de inferência do cálculo. O número de Hajós é então o número mínimo de etapas necessárias para derivar (ou seja, é o comprimento da prova mais curta).χ ( G ) = k + 1 K k + 1 h ( G ) GGχ(G)=k+1Kk+1h(G)G

É muito interessante que:

  • A questão de saber se existe um gráfico cujo é exponencial no tamanho de ainda está em aberto.h ( G ) GGh(G)G
  • Se esse não existir, então .N P = c o N PGNP=coNP
Giorgio Camerani
fonte
5
Repetirei o meu comentário da pergunta a que você vincula, caso você não esteja ciente do teorema (que todos pensam em colorir) de Erdős: Dados os números naturais gek, há um gráfico com perímetro pelo menos ge cromático numere pelo menos k. A circunferência de um gráfico é do tamanho do menor ciclo, o que significa que se você possui circunferências de pelo menos 3, cada clique máximo é do tamanho 2 (cada borda é um clique máximo).
Pål GD
2
Uma observação simples que geralmente é útil: Cada classe de cores é um conjunto independente. Se você pode mostrar que não há um conjunto independente grande, sabe que precisará de muitas cores.
Jukka Suomela
11
Se sempre houvesse uma razão simples para os gráficos serem não- coloráveis, o problema de coloração dos gráficos não seria difícil para NP. A menos que P = NP, alguns gráficos não tenham cores k apenas porque . kk
22412 Jefferson
5
@ Jɛ ff E: um motivo pode ser simples, mas difícil de calcular. Há uma razão bastante simples pela qual um gráfico possui ou não o -Clique, mas ainda é NP-difícil. k
Luke Mathieson

Respostas:

29

Você deve verificar o cálculo do Hajós . Hajós mostrou que todo gráfico com número cromático pelo menos tem um subgrafo que tem uma "razão" para exigir k cores. O motivo em questão é um sistema de prova para exigir k cores. O único axioma é K k , e existem duas regras de inferência. Veja também este artigo de Pitassi e Urquhart sobre a eficiência desse sistema de prova.kkkKk

Yuval Filmus
fonte
11
Excelente, era isso que eu estava procurando.
Giorgio Camerani 26/11/12
11
Obrigado pelo ponteiro. Não conhecia a construção de Hajos anteriormente.
Chandra Chekuri
15

Uma resposta parcial, na qual eu não conheço uma boa "razão" que possa ser generalizada, mas o gráfico a seguir (vergonhoso cortado aqui ):

Gráfico não colorido de 3 sem K4 ou ciclo ímpar com um vizinho completamente conectado

Não é 3-ilusório, mas é, obviamente, de 4 colorable (sendo planar), e não contém qualquer , nem qualquer ciclo com um vértice adicional conectado a todos os vértices de ciclo (a menos que eu estou faltando alguma coisa, mas as únicas vértices conectado a um vértice e seu vizinho estão nos 3 ciclos). Além disso, você pode aplicar uma versão da regra 2 para obter um gráfico do número cromático 5.K4

Eu suspeitaria que, para qualquer gênero, exista um gráfico de um certo número cromático mínimo (veja a conjectura de Heawood ) que não segue as regras 1 ou 2. É claro que não tenho outra prova senão a intuição.

Luke Mathieson
fonte
O gráfico Petersen é um exemplo menor da mesma coisa. No entanto, tanto o gráfico acima como o gráfico Petersen têm menores , que remontam ao comentário acima sobre o Hadwiger. K4
22612 William Macrae
11
Embora a conjectura de Hadwiger seja uma condição necessária, mas não suficiente, um gráfico tem o número cromático se tiver um K k menor e outra coisa . Como JeffE aponta, é claro, é provável que a outra coisa seja apenas porque (no sentido de que não é uma resposta simples). kKk
Luke Mathieson
@LukeMathieson: Extremamente interessante. Você tem um exemplo de gráfico que tem um menor e que é k - 1 para colorir? Kkk1
Giorgio Camerani
5
Pegue um e subdividir todas as arestas. O gráfico resultante é bipartido e, portanto, com duas cores, mas obviamente possui o gráfico completo como menor. Kk
Luke Mathieson
12

Lovasz encontrou obstruções topológicas para a colorabilidade-k e usou sua teoria para resolver a conjectura de Knaser. Seu teorema é o seguinte. Seja G um gráfico conectado e N (G) seja um complexo simplificado cujas faces são subconjuntos de V que possuem vizinhos comuns. Então, se N (K) está conectado em k (ou seja, todos os seus grupos de homologia reduzida são 0 até a dimensão k-1), o número de cores necessárias para colorir G é pelo menos k + 3.

Gil Kalai
fonte
11

Não ter um grande conjunto independente pode ser tão importante quanto ter um grande clique.

Uma obstrução importante para um gráfico não ser k-colorable é que o tamanho máximo de um conjunto independente é menor que n / k, onde n é o número de vértices. Esta é uma obstrução muito importante. Por exemplo, isso implica que um gráfico aleatório em G (n, 1/2) tem um número cromático pelo menos n / log n.

Uma obstrução mais refinada é que, para cada atribuição de pesos não negativos para os vértices, não existe um conjunto independente que capture uma fração 1/5 (ou mais) do peso total. Observe que isso também inclui as "sem obstruções de clique". A dualidade de LP informa que essa obstrução é equivalente ao "número cromático fracionário" de G sendo maior que k.

Também existem obstáculos para a colorabilidade k de natureza diferente que às vezes ultrapassam a barreira do número cromático fracionário. Vou dedicar uma resposta separada a eles.

Gil Kalai
fonte
Obrigado pela sua resposta! A pesos e conjuntos independentes de ligação obstrução mais refinado é extremamente interessante ...
Giorgio camerani
11

Gχ(G)=k+1

Gχ(G)kGk-1 1

David Eppstein
fonte
Obrigado! Definitivamente, é 100% adequado. Ele se encaixa perfeitamente na reformulação da questão.
Giorgio Camerani 02/12/12