Nombre chromatique maximum de graphiques Cayley avec large degré

Question

On sait qu'il n'existe pas d'un graphique régulier de commande $ n $ avec une taille de clique supérieure à $ \ lceil \ frac {n} {2} \ rceil $ . Ma question concerne les graphiques de Cayley avec une large mesure, disons $ \ ge \ frac {n} {2} $ et pas complet . Je pense que le nombre chromatique maximum est $ \ lceil \ frac {3n} {5} \ rceil $ . À titre d'exemple d'un graphique à atteindre l'obtention de la limite supérieure, nous considérons le graphique complet avec la commande divisible par 5 $ et supprimer un $ 2 $ - facteur. Le facteur deux que nous supprimons est l'union disjoint de $ \ frac {n} {5} $ $ 5 $ -Cycles. Ensuite, le nombre chromatique est $ \ frac {3n} {5} $ .

.

Y a-t-il des graphiques de Cayley avec degré $ \ ge \ frac {n} {2} $ , et pas complet, de sorte que leur numéro chromatique dépasse $ \ lceil \ frac {3n} {5} \ rceil $ . Et, aussi, y a-t-il d'autres graphiques de Cayley avec des nombres chromatiques entre $ \ lceil \ frac {n} {2} \ rceil $ et $ \ lceil \ frac {3n} {5} \ rceil $

Answer 1

Erdős and Gallai a montré dans leur papier Solution d'un problème de Dirac Ensuite, le nombre chromatique d'un graphe régulier non complet est au plus $ \ frac {3} {5} n $ .

.

Caccetta et Pullman construit dans leur papier Graphes réguliers avec nombre chromatique prescrit connecté $ k $ $ -Chromatic régulier sur $ n $ sommets pour tous $ k> 1 $ et $ n \ geq \ frac {5} {3} K $ .Vous pouvez vérifier leur construction pour voir si elle peut être adaptée pour donner des graphes de Cayley.