Número cromático máximo de gráficos Cayley com grau grande

Question

Sabe-se que não existe um gráfico regular de ordem $ n $ com tamanho de clique maior que $ \ lcil \ frac {n} {2} \ rceil $ . Minha pergunta se refere aos gráficos de Cayley com grande grau, digamos $ \ GE \ frac {n} {2} $ e não completo . Eu acho que o número cromático máximo é $ \ lceil \ frac {3n} {5} \ rceil $ . Como um exemplo de um gráfico atingindo a obtenção do limite superior, consideramos o gráfico completo com ordem divisível por $ 5 $ e remova uma $ 2 $ - fator. O fator que removemos é a união disjunta de $ \ frac {n} {5} $ $ 5 $ -ciclos. Então, o número cromático é $ \ frac {3n} {5} $ .

Há algum gráfico de Cayley com grau $ \ ge \ frac {n} {2} $ e não é concluído, de forma que seu número cromático exceda a $ \ lceil \ frac {3n} {5} \ rceil $ . E, também há outros gráficos Cayley com números cromáticos entre $ \ lceil \ frac {n} {2} \ rceil $ e $ \ lceil \ frac {3n} {5} \ rceil $

Answer 1

erdős e galai mostrou em seu papel solução de um problema de Dirac então o número cromático de um gráfico regular não completo é no máximo $ \ frac {3} {5} n $ .

Caccetta e Pullman construídos em seu papel gráficos regulares com número cromático prescrito conectado $ k $ -Cromático gráficos regulares na $ n $ vértices para todas as $ k> 1 $ e $ n \ geq \ frac {5} {3} k $ .Você pode verificar sua construção para ver se ele pode ser adaptado para dar gráficos de Cayley.