dbo:abstract
|
- In mathematics, the Heawood number of a surface is an upper bound for the number of colors that suffice to color any graph embedded in the surface. In 1890 Heawood proved for all surfaces except the sphere that no more than colors are needed to color any graph embedded in a surface of Euler characteristic , or genus for an orientable surface. The number became known as Heawood number in 1976. Franklin proved that the chromatic number of a graph embedded in the Klein bottle can be as large as , but never exceeds . Later it was proved in the works of Gerhard Ringel, J. W. T. Youngs, and other contributors that the complete graph with vertices can be embedded in the surface unless is the Klein bottle. This established that Heawood's bound could not be improved. For example, the complete graph on vertices can be embedded in the torus as follows: The case of the sphere is the four-color conjecture, which was settled by Kenneth Appel and Wolfgang Haken in 1976. (en)
- Число Хивуда поверхности — это определённая верхняя граница для максимального числа цветов, необходимых для раскраски любого графа, вложенного в поверхность. В 1890 году Хивуд доказал для всех поверхностей, за исключением сферы, что не более чем цветов необходимо для раскраски любого графа, вложенного в поверхность с эйлеровой характеристикой . Случай сферы соответствует гипотезе о четырёх красках, которую доказали и в 1976 году. Число стало известно как число Хивуда в 1976 году. Франклин доказал, что хроматическое число графа, вложенного в бутылку Кляйна, может достигать , но никогда его не превосходит. Позднее было доказано в работах Герхарда Рингеля и Дж. У. Т. Янгса, что полный граф с вершинами можно вложить в поверхность , за исключением случая, когда является бутылкой Кляйна. Это показывает, что граница Хивуда не может быть улучшена. Например, полный граф с вершинами можно вложить в тор следующим образом: (ru)
|
dbo:thumbnail
| |
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 3386 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
dbp:id
| |
dbp:title
| |
dbp:wikiPageUsesTemplate
| |
dct:subject
| |
rdfs:comment
|
- In mathematics, the Heawood number of a surface is an upper bound for the number of colors that suffice to color any graph embedded in the surface. In 1890 Heawood proved for all surfaces except the sphere that no more than colors are needed to color any graph embedded in a surface of Euler characteristic , or genus for an orientable surface. The number became known as Heawood number in 1976. For example, the complete graph on vertices can be embedded in the torus as follows: The case of the sphere is the four-color conjecture, which was settled by Kenneth Appel and Wolfgang Haken in 1976. (en)
- Число Хивуда поверхности — это определённая верхняя граница для максимального числа цветов, необходимых для раскраски любого графа, вложенного в поверхность. В 1890 году Хивуд доказал для всех поверхностей, за исключением сферы, что не более чем цветов необходимо для раскраски любого графа, вложенного в поверхность с эйлеровой характеристикой . Случай сферы соответствует гипотезе о четырёх красках, которую доказали и в 1976 году. Число стало известно как число Хивуда в 1976 году. Например, полный граф с вершинами можно вложить в тор следующим образом: (ru)
|
rdfs:label
|
- Heawood number (en)
- Число Хивуда (ru)
|
owl:sameAs
| |
prov:wasDerivedFrom
| |
foaf:depiction
| |
foaf:isPrimaryTopicOf
| |
is dbo:wikiPageDisambiguates
of | |
is dbo:wikiPageWikiLink
of | |
is foaf:primaryTopic
of | |