Conjecture de Beraha pour les cycles (French)

cycle d'ordre

3

B(1)	2cos 2π 1 +2	4	4.
B(2)	2cos 2π 2 +2	0	0.
B(3)	2cos 2π 3 +2	1	1.
B(4)	2cos 2π 4 +2	2	2.
B(5)	2cos 2π 5 +2	2+ 1 2 ( 5 -1)	2.61803
B(6)	2cos 2π 6 +2	3	3.
B(7)	2cos 2π 7 +2	2+2sin 3π 14	3.24698
B(8)	2cos 2π 8 +2	2+ 2	3.41421

Le polynôme chromatique d'un graphe donne le nombre de façons de colorier le graphe avec

x

couleurs, sachant que deux sommets reliés ne peuvent pas avoir la même couleur.

La conjecture de Beraha (due à Tutte) dit que tout nombre de Beraha est racine d'un polynôme chromatique, ou au moins limite d'une suite de racines d' une famille de polynômes chromatiques.

Pouvoir manipuler facilement la classe des cycles permet de conjecturer les résultats inédits suivants, qu'il est ensuite facile de prouver mathématiquement:

1) B(4) est racine du polynôme chromatique de tout cycle impair;

2) Pour les cycles d'ordre pair, soit

P

n

la racine de plus grande partie réelle et de partie imaginaire positive, et soit

N

n

, sa complexe conjuguée. Alors les suites

P

n

et

N

n

convergent vers

B(4)

quand

n∞

. Donc

B(4)

est aussi limite de deux suites différentes de racines de polynômes chromatiques.