Hadwiger number
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 k for which the complete graph Kk 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.
Wikipage redirect
Link from a Wikipage to another Wikipage
primaryTopic
Hadwiger number
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 k for which the complete graph Kk 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.
has abstract
En théorie des graphes, le nom ...... is traitable à paramètre fixe.
@fr
In graph theory, the Hadwiger ...... but fixed-parameter tractable.
@en
В теории графов число Хадвигер ...... анно-параметрически разрешима.
@ru
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
1,016,710,499
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
hypernym
type
comment
En théorie des graphes, le nom ...... ue le nombre chromatique de G.
@fr
In graph theory, the Hadwiger ...... as the chromatic number of G.
@en
В теории графов число Хадвигер ...... хроматического числа графа G.
@ru
label
Hadwiger number
@en
Nombre de Hadwiger
@fr
Число Хадвигера
@ru