En théorie des graphes, les graphes de Mycielski, ou myscielkiens, sont des graphes sans triangles de nombre chromatique élevé, construits par récurrence à partir du graphe formé d'un unique sommet par une transformation appelée elle aussi myscielskien. Ils sont dus au mathématicien Jan Mycielski.
Construction
Soit un graphe. Le mycielkien de ce graphe noté est le graphe avec où est une copie de et où et .
Les graphes de Mycielski sont les graphes définis par la récurrence suivante : est le graphe à une arête, et .
Propriétés Si le nombre chromatique de G est k, alors celui de M(G) est k+1. Si G est sans triangle, alors M(G) aussi. Si G possède un cycle hamiltonien, alors M(G) aussi. Si le nombre de domination de G est γ(G), alors celui de M(G) est γ(G)+1.
Bibliographie
. . . . .
Notes et références
Liens externes
Catégorie:Famille de graphes