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

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'\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})$.

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

• (en) Valerie King, « A Simpler Minimum Spanning Tree Verification Algorithm », Algorithmica, vol. 18, n^o 2,‎ 1997, p. 263-270

• (en) Vašek Chvátal, « The minimality of the Mycielski graph », Graphs and Combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973),‎ 1974
• (en) Tomislav Došlić, « Mycielskians and matchings », Discussiones Mathematicae Graph Theory, vol. 25,‎ 2005.
• (en) David C. Fisher, Patricia A. McKenna et Elizabeth D. Boyer, « Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski's graphs », Discrete Applied Mathematics, vol. 84,‎ 1998, p. 93–105 (DOI 10.1016/S0166-218X(97)00126-1).
• Wensong Lin, Jianzhuan Wu, Peter Che Bor Lam et Guohua Gu, « Several parameters of generalized Mycielskians », Discrete Applied Mathematics, vol. 154, n^o 8,‎ 2006, p. 1173–1182 (DOI 10.1016/j.dam.2005.11.001).
• Jan Mycielski, « Sur le coloriage des graphes », Colloq. Math., vol. 3,‎ 1955, p. 161–162 (lire en ligne).
• C. Tardif, « Fractional chromatic numbers of cones over graphs », Journal of Graph Theory, vol. 38, n^o 2,‎ 2001, p. 87–94 (DOI 10.1002/jgt.1025).

Liens externes

• (en) Eric W. Weisstein, « Graphe de Mycielski », sur MathWorld