Graphe de Mycielski
# 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.
