| 翻訳と辞書 |
Mycielskian
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.
==Construction==
Let the ''n'' vertices of the given graph ''G'' be ''v''0, ''v''1, etc. The Mycielski graph μ(''G'') of ''G'' contains ''G'' itself as an isomorphic subgraph, together with ''n''+1 additional vertices: a vertex ''u''''i'' corresponding to each vertex ''v''''i'' of ''G'', and another vertex ''w''. Each vertex ''u''''i'' is connected by an edge to ''w'', so that these vertices form a subgraph in the form of a star ''K''1,''n''. In addition, for each edge ''v''''i''''v''''j'' of ''G'', the Mycielski graph includes two edges, ''u''''i''''v''''j'' and ''v''''i''''u''''j''.
Thus, if ''G'' has ''n'' vertices and ''m'' edges, μ(''G'') has 2''n''+1 vertices and 3''m''+''n'' edges.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Mycielskian」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|