Graphe de Mycielski

Modèle:Voir homonymes 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

Le graphe de Grötzsch $M_4$ construit comme le mycielkien du graphe-cycle à 5 sommets M_3

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^{\prime }\cup \{u\}$ où $V^{\prime }$ est une copie de $V$ et $E_M=E\cup E^{\prime }\cup E^{″}$ où $E^{\prime }=\{\{u,v^{\prime }\}|v^{\prime }\in V^{\prime }\}$ et $E^{″}=\{\{v_i,{v_j}^{\prime }\}|v_i\in V,{v_j}^{\prime }\in V^{\prime },\{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)$.

Graphes de Mycielski M₂, M₃ et M₄

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

• Modèle:Article

• Modèle:Article
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.

Liens externes

• Modèle:MathWorld