Beaucoup de resultats traitent du nombre chromatique des graphes sans
triangle, et plus specifiquement des graphes sans triangles ayant
beaucoup d'aretes (le theoreme de Turan par exemple). Dans ce
contexte, Hajnal a prouve que pour tout epsilon > 0, on peut trouver
des graphes sans triangle de degre minimum au moins (1/3 - epsilon)n
de nombre chromatique arbitrairement grand (avec n le nombre de
sommets du graphe). Sa construction est basee sur des graphes de Kneser
sans triangle de grand nombre chromatique.
Cependant cette construction ne peut pas etre etendue pour des graphes
de degre minimum >n/3 et en 1972, Erdos et Simonovits ont demande si
le nombre chromatique pouvait etre borne dans ce cas. Ils croyaient
que 3 pouvait etre une borne superieure mais Haggkvist a trouve un
graphe 10-regulier a 29 sommets 4-chromatique.
Plus tard, Jin a montre que si le degre minimum est au moins 10n/29 alors
le nombre chromatique est au plus 3.
La premiere borne dans le cas general a ete donnee pas Thomassen:
il a prouve que pour tout epsilon>0, le nombre chromatique des graphes sans triangles de degre minimum au moins (1/3 + epsilon)n est borne par une constante
c dependant de epsilon, avec c tendant vers l'infini quand epsilon tend vers 0.
Avec S. Brandt (Ilmenau T. Univ.), nous resolvons completement le
probleme en prouvant que les graphes sans triangles de degre minimum
superieur a n/3 sot 4-colorables. Dans cet expose, cette preuve qui utilise un peu de programmation lineaire est presentee.