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 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\}V' est une copie de V et  E_M = E\cup E' \cup E'' 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_0= (x,\emptyset) et  M_{n+1}=M(M_n).

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,‎ 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, Wu, Peter Che Bor Lam et Gu, « Several parameters of generalized Mycielskians », Discrete Applied Mathematics, vol. 154, no 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, no 2,‎ 2001, p. 87–94 (DOI 10.1002/jgt.1025).

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

Liens externes[modifier | modifier le code]