Graafiteoriassa suuntaamattoman graafin G Hadwiger -luku on suurimman täydellisen graafin koko, joka voidaan saada supistamalla G : n reunoja . Vastaavasti Hadwigerin luku h ( G ) on suurin luku k , jolle täydellinen graafi K k on G :n molli , pienempi graafi, joka saadaan G : stä supistamalla reunoja ja poistamalla kärjet ja reunat. Hadwiger-luku tunnetaan myös graafin G klikkin supistumisen numerona [1] tai graafin G homomorfismin asteena [2] . Numero on nimetty Hugo Hadwigerin mukaan, joka esitteli luvun vuonna 1943 ja arveli , että Hadwiger-luku on aina vähintään graafin G kromaattinen luku .
Graafit, joiden Hadwiger-luku on 4 tai vähemmän, kuvaa Wagner [3] . Graafit, joissa on mikä tahansa äärellinen Hadwiger-luku, ovat harvassa ja niissä on pieni kromaattinen luku. Hadwiger-luvun määrittäminen kuvaajalle on NP-vaikea , mutta ongelma on ratkaistavissa kiinteän parametrin avulla.
Graafilla G on Hadwiger-luku enintään 2, jos ja vain jos se on metsä ja kolmipisteinen täydellinen molli voidaan muodostaa supistamalla sykli G :ssä .
Graafilla on Hadwiger -luku kolme tai vähemmän, jos ja vain, jos sen puunleveys ei ylitä kahta, mikä pätee silloin ja vain, jos jokin sen saranoista on rinnakkaissarjakuvaaja .
Wagnerin lauseesta , joka kuvaa tasograafit niiden kiellettyjen aligraafien avulla , seuraa, että tasograafien Hadwiger-luku on enintään 4. Joissakin lauseen todistuksen sisältävissä artikkeleissa Wagner [3] kuvaa graafeja, joiden Hadwiger-luku on neljä tai vähemmän. tarkemmin sanottuna - nämä ovat graafeja, jotka voidaan muodostaa tasograafien summa -klikki- operaatioilla Wagner-graafilla , jossa on 8 kärkeä.
Graafit, joiden Hadwiger-luku on alle viisi, sisältävät huippupistegraafit ja linkittömät upotettavat graafit , molemmilla perheillä on täydellinen graafi K 6 kiellettyjen alaikäisten joukossa [4]
Jokaisella graafilla, jossa on n kärkeä ja Hadwiger-luku k , on O( nk √ log k ) reunaa. Tämä raja on tarkka – mille tahansa k :lle on olemassa graafi, jolla on Hadwiger-luku k ja jolla on Ω( nk √ log k ) reunat [5] [6] [7] . Jos graafilla G on Hadwiger-luku k , niin kaikilla sen aligraafilla on myös Hadwiger-luku enintään k , mikä tarkoittaa, että graafilla G on oltava degeneraatio O( k √ log k ). Siten graafit, joissa on rajoitettu Hadwiger-luku, ovat harvalukuisia .
Hadwiger-oletus väittää, että Hadwiger-luku on aina vähintään graafin G kromaattinen luku . Toisin sanoen minkä tahansa graafin, jolla on Hadwiger-luku k , tulee värittää enintään k väriä. Tapaus k = 4 vastaa (Wagnerin luonnehdinnalla kuvaajia tällä Hadwiger-luvulla) tasograafien värjäyksen neliväriongelmaa . Hypoteesi on myös todistettu arvolle k ≤ 5, mutta se jää todistamatta suurille k :n arvoille [8]
Pienen tiheyden vuoksi graafit, joiden Hadwiger-luku on enintään k , voidaan värjätä ahneella väritysalgoritmilla O( k √ log k ) -väreillä.
Sen tarkistaminen, onko tietyn graafin Hadwiger-luku suurempi kuin jokin arvo k , on NP-täydellinen tehtävä [9] , mikä tarkoittaa, että Hadwiger-luvun määrittäminen on NP-kova ongelma . Ongelma on kuitenkin kiinteä-parametrisesti ratkaistavissa — on olemassa algoritmi, jolla määritetään ajallisesti suurin klikkausmolli, joka riippuu vain polynomiaalisesti graafin koosta, mutta eksponentiaalisesti h ( G ) [10] . Lisäksi polynomiaikaalgoritmit voivat approksimoida Hadwiger-luvun paljon tarkemmin kuin paras polynomiajan approksimaatio (olettaen P ≠ NP) suurimpien täydellisten aligraafien koosta [10] .
Graafin G akromaattinen luku on suurimman klikkin koko, joka voidaan muodostaa supistamalla riippumattomien joukkojen perhe G :ssä .
Laskemattomat klikki-mollit äärettömissä kaavioissa voidaan luonnehtia suojilla , jotka formalisoivat väistöstrategiat joissakin takaa-ajo- välttöpeleissä - jos Hadwiger-luku on laskematon, se on yhtä suuri kuin kaavion suurimman suojan kertaluku [11] .
Jokaisella graafilla, jolla on Hadwiger-luku k , on korkeintaan n 2 O( k log log k ) klikkia (täydellisiä aligraafia) [12] .
Halin [2] määritteli graafiparametrien luokan, jota hän kutsui S -funktioiksi. Niiden joukossa on Hadwiger-numero. Näiden funktioiden, jotka yhdistävät graafit kokonaislukuihin, vaaditaan ottamaan nolla reunattomissa kaavioissa , olemaan vähäisiä monotonisia , kasvamaan yhdellä, kun lisätään uusi kärki kaikkien aikaisempien kärkien viereen, ja kahdesta arvosta aligraafien molemmilla puolilla klikkierotinta funktio. pitäisi saada suurempi arvo. Tällaisten funktioiden joukko muodostaa täydellisen hilanottamalla minimi- tai maksimielementit. Tällaisen hilan alaelementti on Hadwiger-luku ja ylin elementti puunleveys .