| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén egy G irányítatlan gráf Hadwiger-száma annak a legnagyobb teljes gráfnak a mérete, ami G éleinek összehúzásával előállítható.Ezzel ekvivalens megfogalmazás szerint a h(G) Hadwiger-szám megegyezik annak a legnagyobb Kk teljes gráfnak a k méretével, ami G-nek minora, azaz előállítható belőle az élösszehúzás, csúcstörlés és éltörlés műveletek segítségével. Úgy is ismert, mint G összehúzási klikkszáma (contraction clique number) vagy G homomorfizmus-foka (homomorphism degree). Nevét kapta, aki 1943-ban a Hadwiger-sejtés kapcsán bevezette; a sejtés állítása szerint a Hadwiger-szám minden esetben legalább akkora, mint G kromatikus száma. A legfeljebb négy Hadwiger-számú gráfok jellemzését végezte el. A korlátos Hadwiger-számú gráfok ritkák, kromatikus számuk alacsony. Egy gráf Hadwiger-számának megállapítása , de . (hu)
- A matematika, azon belül a gráfelmélet területén egy G irányítatlan gráf Hadwiger-száma annak a legnagyobb teljes gráfnak a mérete, ami G éleinek összehúzásával előállítható.Ezzel ekvivalens megfogalmazás szerint a h(G) Hadwiger-szám megegyezik annak a legnagyobb Kk teljes gráfnak a k méretével, ami G-nek minora, azaz előállítható belőle az élösszehúzás, csúcstörlés és éltörlés műveletek segítségével. Úgy is ismert, mint G összehúzási klikkszáma (contraction clique number) vagy G homomorfizmus-foka (homomorphism degree). Nevét kapta, aki 1943-ban a Hadwiger-sejtés kapcsán bevezette; a sejtés állítása szerint a Hadwiger-szám minden esetben legalább akkora, mint G kromatikus száma. A legfeljebb négy Hadwiger-számú gráfok jellemzését végezte el. A korlátos Hadwiger-számú gráfok ritkák, kromatikus számuk alacsony. Egy gráf Hadwiger-számának megállapítása , de . (hu)
|
