Estou procurando um pequeno gráfico cujo número cromático vetorial é menor que o número cromático, .
( tem vector número cromática se houver uma atribuição , em que intuitivamente os vectores associados com vértices vizinhos estão distantes O requisito é. Por exemplo, para , os vértices de um triângulo são suficientes.
O número cromático vetorial de um gráfico não é maior que o número cromático: . São conhecidos exemplos de gráficos com . (O artigo original de Karger, Motwani, Sudão [JACM, 45: 246-265] ( manuscrito ) sugere gráficos generalizados de Kneser, um artigo mais recente usa uma construção baseada em vetores de unidades aleatórias.)
Eu acho que tenho um exemplo de gráfico com e (com base no cálculo por computador). Este gráfico possui 20 vértices e 90 arestas.
Existe um exemplo menor? Uma avenida tentadora seria fornecer um vetor concreto de 3 cores do gráfico Chvatal ou Grötzsch, se esse animal existir.
( não precisa ser um número inteiro, mas seria bom. Atualização: Como apontado abaixo, o caso não-íntegro é realmente fácil. Obrigado.)
Atualização: Grötzsch e Chvátal
Não pude resistir a pensar no vetor 3 para colorir os gráficos de Chvátal e Grötzsch.
O gráfico de Grötsch pode ser do vetor 3 colorido da seguinte maneira: Coloque o nó do grau cinco no pólo norte. Os nós de 5 graus-4 são colocados uniformemente na mesma latitude, a cerca de 77 graus do norte: imagine um pentagrama pintado no hemisfério norte da Terra. Os 5 nós restantes (de grau 3) terminam no hemisfério sul, a cerca de 135 graus do norte. Eles têm a mesma longitude que os outros 5. (Carregarei um desenho quando tiver um, mas é mais difícil desenhar linhas geodésicas no TikZ do que eu pensava.)
De acordo com um solucionador de SDP, Chvátal também admite um vetor de 3 cores, mas a saída é apenas um monte de vetores em 5 dimensões que eu tenho dificuldades em interpretar.
(Uma terceira tentativa falhou: inspirado na construção de Yury, pegue o ciclo 5 e adicione um vértice no ápice adjacente a todos os outros. Este gráfico tem o número cromático 4. Mas, de acordo com o meu solucionador, não é um vetor 3 colorido.)
fonte
Respostas:
fonte
Aqui está uma incorporação do gráfico de Grötzsch na esfera unitária: corresponde a um vetor colorido da maneira óbvia; por exemplo, o vértice no polo norte é colorido com o vetor (0,0,1).
O gráfico de Grötsch possui 3 tipos de nós. Um único grau 5 nós (no norte). Cinco nós de grau 4 (no hemisfério Norte, equidistante de N, você pode distinguir três deles). Cinco nós de grau 3 (no hemisfério sul, equidistante de N, você pode distinguir 3 deles).
N está conectado aos seus 5 vizinhos no hemisfério sul com bordas verdes. (Observe que a borda verde parece ter ocorrido nos graus 4-vértices no hemisfério norte, mas isso é um artefato da incorporação.)
Visto de cima, você pode fazer o pentagrama descrito pelo grau 4 nós, semelhante a Lovasz' incorporação de no plano:C5
Finalmente, uma visão de cima do pólo sul:
Se meus cálculos são confiáveis, todos os vértices vizinhos estão a mais de 120 graus um do outro, então isso constitui um vetor 3-color válido. O gráfico de Grötzsch é 4-cromático. 11 vértices, 20 arestas. Estou particularmente feliz com este exemplo, porque a coloração do vetor está em três dimensões, para você poder visualizá-la. (E desenhe hiperplanos aleatórios para explicar o algoritmo de coloração do gráfico KMS.)
fonte