Número cromático máximo de gráficos de Cayley con gran grado

Question

Se sabe que no existe una gráfica regular de orden $ n $ con el tamaño de la clama mayor que $ \ lceil \ frac {n} {2} \ rceil $ . Mi pregunta se refiere a los gráficos de Cayley con gran título, por ejemplo, $ \ ge \ frac {n} {2} $ y no completo . Creo que el número cromático máximo es $ \ lceil \ frac {3n} {5} \ rceil $ . Como ejemplo de un gráfico que logra el logro del límite superior, consideramos el gráfico completo con el pedido divisible por $ 5 $ y elimine un $ 2 $ - Factor. Los dos factores que eliminamos es la unión de disjoint de $ \ frac {n} {5} $ $ 5 $ -Ciclos. Luego, el número cromático es $ \ frac {3n} {5} $ .

¿Hay algún gráfico de Cayley con grado $ \ ge \ frac {n} {2} $ , y no complete, de modo que su número cromático exceda $ \ lceil \ frac {3n} {5} \ rceil $ . Y, también, hay otros gráficos de Cayley con números cromáticos entre $ \ lceil \ frac {n} {2} \ rceil $ y $ \ lceil \ frac {3n} {5} \ rceil $

Answer 1

Erdős y Gallai se mostraron en su papel Solución de un problema de Dirac Luego, el número cromático de un gráfico regular no completo está en la mayoría de $ \ frac {3} {5} n $ .

Caccetta y Pullman construidos en su papel Gráficos regulares con el número cromático prescrito conectado $ k $ -chromatic regular gráficos en $ n $ vértices para todos $ k> 1 $ y $ n \ geq \ frac {5} {3} K $ .Puede verificar su construcción para ver si se puede adaptar para dar gráficos de Cayley.