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:k
- contém uma camarilha do tamanho . Esta é a razão óbvia.
Existe um subgrafo de modo que as duas afirmações a seguir são verdadeiras:G
- não é colorável.
- . Em outras palavras, existe um nó em , mas não em , de tal modo que está ligado a cada nó em .G H x H
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 + 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 + 1
- 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 + 1
Questão
Existe algum outro motivo, além daqueles 2 acima, que torna um gráfico não colorido?
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 + 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 ) 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 ) G
- Se esse não existir, então .N P = c o N P
fonte
Respostas:
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.k k k Kk
fonte
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 ):
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.
fonte
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.
fonte
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.
fonte
fonte