Graphe de Mycielski

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes, les graphes de Mycielski, ou myscielkiens, sont des graphes sans triangles de nombre chromatique élevé, construit 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[modifier | modifier le code]

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

Soit un graphe. Le mycielkien de ce graphe noté est le graphe avec est une copie de et et .

Les graphes de Mycielski sont les graphes définis par la récurrence suivante : et .

Graphes de Mycielski M2, M3 et M4

Propriétés[modifier | modifier le code]

  • Si le nombre chromatique de G est k, alors celui de M(G) est k+1[1].
  • Si G est sans triangle, alors M(G) aussi[1].
  • Si G possède un cycle hamiltonien, alors M(G) aussi[2].
  • Si le nombre de domination de G est γ(G), alors celui de M(G) est γ(G)+1[2].

Bibliographie[modifier | modifier le code]

  • (en) Valerie King, « A Simpler Minimum Spanning Tree Verification Algorithm », Algorithmica, vol. 18, no 2,‎ , 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),‎
  • (en) Tomislav Došlić, « Mycielskians and matchings », Discussiones Mathematicae Graph Theory, vol. 25,‎ .
  • (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,‎ , p. 93–105 (DOI 10.1016/S0166-218X(97)00126-1).
  • Wensong Lin, Wu, Peter Che Bor Lam et Gu, « Several parameters of generalized Mycielskians », Discrete Applied Mathematics, vol. 154, no 8,‎ , p. 1173–1182 (DOI 10.1016/j.dam.2005.11.001).
  • Jan Mycielski, « Sur le coloriage des graphes », Colloq. Math., vol. 3,‎ , p. 161–162 (lire en ligne).
  • C. Tardif, « Fractional chromatic numbers of cones over graphs », Journal of Graph Theory, vol. 38, no 2,‎ , p. 87–94 (DOI 10.1002/jgt.1025).

Notes et références[modifier | modifier le code]

Liens externes[modifier | modifier le code]