Gráfico pequeno com intervalo entre número cromático e número cromático vetorial?

12

Estou procurando um pequeno gráfico G cujo número cromático vetorial é menor que o número cromático, χv(G)<χ(G) .

( G tem vector número cromática q se houver uma atribuição x:VRd , em que intuitivamente os vectores associados com vértices vizinhos estão distantes O requisito é. x(v),x(w)1/(q1) Por exemplo, para q=3 , 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: χv(G)χ(G) . São conhecidos exemplos de gráficos com χv(G)=3 χ(G)=nδ . (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 K com χv(K)=4 e χ(K)=8 (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.

( χv 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.)

Thore Husfeldt
fonte
1
Você poderia fornecer um link ou uma definição para o número cromático do vetor?
Suresh Venkat
4
χv(C5)=5<3=χ(C5)C5C5Gχv(G)χ(G)

Respostas:

7

χv(G)G=C5

χv(C5)=5<3=χ(C5).[Lovász]

χv(G)G1C5(1)C5(2)C5(1)C5(2)G2=K5GG1G2

χ(G)=max(χ(G1),χ(G2))=χ(G1)=6.χv(G)=max(χv(G1),χv(G2))=max(25,5)=5.
Yury
fonte
3

Aqui está uma incorporação do gráfico de Grötzsch na esfera unitária: insira a descrição da imagem aqui 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:C5insira a descrição da imagem aqui

Finalmente, uma visão de cima do pólo sul: insira a descrição da imagem aqui

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.)

Thore Husfeldt
fonte