| dbo:abstract
|
- In graph theory, the Hadwiger number of an undirected graph G is the size of the largest complete graph that can be obtained by contracting edges of G.Equivalently, the Hadwiger number h(G) is the largest number n for which the complete graph Kn is a minor of G, a smaller graph obtained from G by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of G or the homomorphism degree of G. It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of G. The graphs that have Hadwiger number at most four have been characterized by . The graphs with any finite bound on the Hadwiger number are sparse, and have small chromatic number. Determining the Hadwiger number of a graph is NP-hard but fixed-parameter tractable. (en)
- En théorie des graphes, le nombre de Hadwiger d'un graphe non orienté G est la taille du plus grand graphe complet qui peut être obtenu en contractant des arêtes de G. De manière équivalente, le nombre de Hadwiger h(G) est le plus grand entier k pour lequel le graphe complet K k est un mineur de G. Le nombre de Hadwiger est également connu comme le nombre de clique de contraction de G ou le degré d'homomorphisme de G. Il est nommé d'après Hugo Hadwiger, qui l'a introduit en 1943 en conjonction avec la conjecture de Hadwiger qui stipule que le nombre de Hadwiger est toujours au moins aussi grand que le nombre chromatique de G. Les graphes qui ont un nombre de Hadwiger au plus égal à quatre ont été caractérisés par Wagner en 1937. Les graphes qui ont un nombre de Hadwiger fini borné sont peu denses et ont aussi un petit nombre chromatique. La détermination du nombre de Hadwiger d'un graphe est NP-difficile mais traitable à paramètre fixe. (fr)
- В теории графов число Хадвигера неориентированного графа G — это размер наибольшего полного графа, который может быть получен стягиванием рёбер графа G.Эквивалентно, число Хадвигера h(G) — это наибольшее число k, для которого полный граф Kk является минором графа G, меньший граф, полученный из G стягиванием рёбер и удалением вершин и рёбер. Число Хадвигера известно также как число кликового стягивания графа G или степень гомоморфизма графа G. Число названо именем Гуго Хадвигера, который ввёл число в 1943 и высказал гипотезу, по которой число Хадвигера всегда не меньше хроматического числа графа G. Графы, имеющие число Хадвигера 4 и менее, описаны Вагнером. Графы с любым конечным числом Хадвигера разрежены и имеют малое хроматическое число. Определение числа Хадвигера для графа является NP-трудной задачей, но задача фиксированно-параметрически разрешима. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 11342 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In graph theory, the Hadwiger number of an undirected graph G is the size of the largest complete graph that can be obtained by contracting edges of G.Equivalently, the Hadwiger number h(G) is the largest number n for which the complete graph Kn is a minor of G, a smaller graph obtained from G by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of G or the homomorphism degree of G. It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of G. (en)
- En théorie des graphes, le nombre de Hadwiger d'un graphe non orienté G est la taille du plus grand graphe complet qui peut être obtenu en contractant des arêtes de G. De manière équivalente, le nombre de Hadwiger h(G) est le plus grand entier k pour lequel le graphe complet K k est un mineur de G. Le nombre de Hadwiger est également connu comme le nombre de clique de contraction de G ou le degré d'homomorphisme de G. Il est nommé d'après Hugo Hadwiger, qui l'a introduit en 1943 en conjonction avec la conjecture de Hadwiger qui stipule que le nombre de Hadwiger est toujours au moins aussi grand que le nombre chromatique de G. (fr)
- В теории графов число Хадвигера неориентированного графа G — это размер наибольшего полного графа, который может быть получен стягиванием рёбер графа G.Эквивалентно, число Хадвигера h(G) — это наибольшее число k, для которого полный граф Kk является минором графа G, меньший граф, полученный из G стягиванием рёбер и удалением вершин и рёбер. Число Хадвигера известно также как число кликового стягивания графа G или степень гомоморфизма графа G. Число названо именем Гуго Хадвигера, который ввёл число в 1943 и высказал гипотезу, по которой число Хадвигера всегда не меньше хроматического числа графа G. (ru)
|
| rdfs:label
|
- Nombre de Hadwiger (fr)
- Hadwiger number (en)
- Число Хадвигера (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
