title: Graphe de Mycielski
text: # Graphe de Mycielski
  
  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 $G=(V,E)$ un graphe. Le mycielkien de ce graphe noté $M(G)$ est le graphe $(V_{M},E_{M})$ avec $V_{M}=V\cup V'\cup \{u\}$ où $V'$ est une copie de $V$ et $E_{M}=E\cup E'\cup E''$ où $E'=\{\{u,v'\}|v'\in V'\}$ et $E''=\{\{v_{i},v_{j}'\}|v_{i}\in V,v_{j}'\in V',\{v_{i},v_{j}\}\in E\}$.
  
  Les graphes de Mycielski sont les graphes $M_{n}$ définis par la récurrence suivante : $M_{2}$ est le graphe à une arête, et $M_{n+1}=M(M_{n})$.
  
  ## 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.
  