Tous les graphes critiques de Ramsey pour de grands cycles contre un graphe complet d'ordre six

Un nouveau domaine de la théorie des graphes qui a émergé au cours des dernières décennies est le calcul des nombres de Ramsey critiques en étoile liés à différentes classes de graphes. Formellemnt, nous dirons que Kn → (G,H) si, pour toute coloration de Kn, il existe une copie de G dans la première couleur, rouge, ou une copie de H dans la seconde couleur, bleue. Le nombre de Ramsey r(G,H) est défini comme le plus petit entier positif n tel que Kn → (G,H). Un concept étroitement lié au nombre de Ramsey est le nombre de Ramsey critique en étoile r∗(G,H), défini comme la plus grande valeur de k tel que Kr(G,H)−1 ⊔ K1,k → (G,H). Une coloration à deux couleurs de Kr(G,H)−1 telle que Kr(G,H)−1 ̸→ (G,H) est appelée une coloration critique de Ramsey. Un graphe critique de Ramsey r(G,H) est un graphe induit par la première couleur d'une coloration critique de Ramsey. Les bornes inférieures des nombres de Ramsey critiques en étoile sont généralement trouvées avec l'aide de graphes critiques de Ramsey. Le problème particulier que nous abordons dans cet article, sur les nombres de Ramsey critiques en étoile, est basé sur une conjecture formulée en 1973 par Bondy et Erdős concernant les nombres de Ramsey pour de grands cycles par rapport aux graphes complets. Basé sur certains lemmas que nous présentons avec une preuve, de plus nous montrons qu'il existe exactement soixante-huit graphes critiques de Ramsey r(Cn,K6) non-isomorphes, lorsque n ≥ 15.