Graphe de Chvátal
Le graphe de Chvátal est hamiltonien et sans triangle. Il joue un rôle clef dans l'article de Herbert Fleischner et Gert Sabidussi (en) prouvant en 2002 que déterminer si un graphe hamiltonien sans triangle est 3-colorable est un problème NP-complet.
Article Wikipédia (CC BY-SA 4.0)