Concept

Graphe de Mycielski

In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph is a larger graph formed from it by a construction of . The construction preserves the property of being triangle-free but increases the chromatic number; by applying the construction repeatedly to a triangle-free starting graph, Mycielski showed that there exist triangle-free graphs with arbitrarily large chromatic number. Let the n vertices of the given graph G be v1, v2, . . . , vn. The Mycielski graph μ(G) contains G itself as a subgraph, together with n+1 additional vertices: a vertex ui corresponding to each vertex vi of G, and an extra vertex w. Each vertex ui is connected by an edge to w, so that these vertices form a subgraph in the form of a star K1,n. In addition, for each edge vivj of G, the Mycielski graph includes two edges, uivj and viuj. Thus, if G has n vertices and m edges, μ(G) has 2n+1 vertices and 3m+n edges. The only new triangles in μ(G) are of the form vivjuk, where vivjvk is a triangle in G. Thus, if G is triangle-free, so is μ(G). To see that the construction increases the chromatic number , consider a proper k-coloring of ; that is, a mapping with for adjacent vertices x,y. If we had for all i, then we could define a proper (k−1)-coloring of G by when , and otherwise. But this is impossible for , so c must use all k colors for , and any proper coloring of the last vertex w must use an extra color. That is, . Applying the Mycielskian repeatedly, starting with the one-edge graph, produces a sequence of graphs Mi = μ(Mi−1), sometimes called the Mycielski graphs. The first few graphs in this sequence are the graph M2 = K2 with two vertices connected by an edge, the cycle graph M3 = C5, and the Grötzsch graph M4 with 11 vertices and 20 edges. In general, the graph Mi is triangle-free, (i−1)-vertex-connected, and i-chromatic. The number of vertices in Mi for i ≥ 2 is 3 × 2i−2 − 1 , while the number of edges for i = 2, 3, . . . is: 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... .

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.