Mycielskian (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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. (fr) 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 Jan Mycielski. 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. (en) Graf Mycielskiego lub Mycielskian nieskierowanego grafu G – graf μ(G) stworzony dzięki konstrukcji podanej przez Jana Mycielskiego w roku 1955, pokazującej istnienie grafu, w którym największa klika ma rozmiar ≤ 2, o bezwzględnie dużej liczbie chromatycznej. Uogólniona wersja konstrukcji została przedstawiona przez w roku 2006. (pl) Мичельськіа́н або граф Миче́льського неорієнтованого графа — граф, отриманий застосуванням побудови. Побудова зберігає відсутність трикутників, але збільшує хроматичне число. Мичельський показав, що застосовуючи пробудову повторно до початкового графа без трикутників, можна отримати графи без трикутників довільно великого розміру. (uk) Мычельскиан или граф Мычельского неориентированного графа — граф, созданный применением конструкции Мычельского.Конструкция сохраняет отсутствие треугольников, но увеличивает хроматическое число.Мычельский показал, что повторяя конструкцию повторно к начальному графу без треугольников, можно получить графы без треугольников произвольно большого размера. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Mycielskian_construct...1-vertex_Grotzsch_graph.png?width=300 |
| dbo:wikiPageExternalLink | http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3119.pdf |
| dbo:wikiPageID | 7685346 (xsd:integer) |
| dbo:wikiPageLength | 8893 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1094481739 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Undirected_graph dbr:Domination_number dbr:Topological_combinatorics dbr:Mathematics dbr:Chromatic_number dbr:László_Lovász dbr:Clique_number dbr:Triangle-free_graph dbr:K-vertex-connected_graph dbr:Cycle_graph dbr:Graph_theory dbr:Technische_Universität_Ilmenau dbr:Tensor_product_of_graphs dbc:Graph_operations dbr:Grötzsch_graph dbr:Kneser_graph dbr:Factor-critical_graph dbr:Odd_girth dbr:Hamiltonian_cycle dbr:File:Generalized_Mycielskian.svg dbr:File:Mycielski_graph_k4_hamiltonian_path.svg dbr:File:Mycielski_graphs.svg dbr:File:Mycielskian_construction_of_11-vertex_Grotzsch_graph.png |
| dbp:authorlink | Jan Mycielski (en) |
| dbp:first | Jan (en) |
| dbp:last | Mycielski (en) |
| dbp:title | Mycielski Graph (en) |
| dbp:urlname | MycielskiGraph (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harv dbt:Harvtxt dbt:Mathworld dbt:OEIS dbt:Short_description dbt:Harvs |
| dbp:year | 1955 (xsd:integer) |
| dcterms:subject | dbc:Graph_operations |
| rdf:type | yago:Abstraction100002137 yago:Action114006945 yago:Attribute100024264 yago:Communication100033020 yago:Graph107000195 yago:Operation114008806 yago:WikicatGraphOperations yago:WikicatGraphs yago:State100024720 yago:VisualCommunication106873252 |
| rdfs:comment | 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. (fr) 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 Jan Mycielski. 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. (en) Graf Mycielskiego lub Mycielskian nieskierowanego grafu G – graf μ(G) stworzony dzięki konstrukcji podanej przez Jana Mycielskiego w roku 1955, pokazującej istnienie grafu, w którym największa klika ma rozmiar ≤ 2, o bezwzględnie dużej liczbie chromatycznej. Uogólniona wersja konstrukcji została przedstawiona przez w roku 2006. (pl) Мичельськіа́н або граф Миче́льського неорієнтованого графа — граф, отриманий застосуванням побудови. Побудова зберігає відсутність трикутників, але збільшує хроматичне число. Мичельський показав, що застосовуючи пробудову повторно до початкового графа без трикутників, можна отримати графи без трикутників довільно великого розміру. (uk) Мычельскиан или граф Мычельского неориентированного графа — граф, созданный применением конструкции Мычельского.Конструкция сохраняет отсутствие треугольников, но увеличивает хроматическое число.Мычельский показал, что повторяя конструкцию повторно к начальному графу без треугольников, можно получить графы без треугольников произвольно большого размера. (ru) |
| rdfs:label | Graphe de Mycielski (fr) Mycielskian (en) Graf Mycielskiego (pl) Мычельскиан (ru) Мичельськіан (uk) |
| owl:sameAs | freebase:Mycielskian yago-res:Mycielskian wikidata:Mycielskian dbpedia-fr:Mycielskian dbpedia-hu:Mycielskian dbpedia-pl:Mycielskian dbpedia-ru:Mycielskian dbpedia-uk:Mycielskian https://global.dbpedia.org/id/57GJA |
| prov:wasDerivedFrom | wikipedia-en:Mycielskian?oldid=1094481739&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Generalized_Mycielskian.svg wiki-commons:Special:FilePath/Mycielski_graph_k4_hamiltonian_path.svg wiki-commons:Special:FilePath/Mycielski_graphs.svg wiki-commons:Special:FilePath/Mycielskian_construction_of_11-vertex_Grotzsch_graph.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Mycielskian |
| is dbo:wikiPageDisambiguates of | dbr:Mycielski |
| is dbo:wikiPageRedirects of | dbr:Mycielski_graph |
| is dbo:wikiPageWikiLink of | dbr:Mycielski dbr:Jan_Mycielski dbr:Girth_(graph_theory) dbr:Graph_coloring dbr:Graph_homomorphism dbr:Triangle-free_graph dbr:Graph_operations dbr:Grötzsch's_theorem dbr:Grötzsch_graph dbr:Simplex_graph dbr:Factor-critical_graph dbr:Mycielski_graph |
| is foaf:primaryTopic of | wikipedia-en:Mycielskian |
