I grafteorin är Hadwiger-talet för en oriktad graf G storleken på den största kompletta grafen som kan erhållas genom att dra ihop kanterna på G . På motsvarande sätt är Hadwigertalet h ( G ) det största talet k för vilket hela grafen K k är en mindre av G , den mindre grafen erhålls från G genom att dra ihop kanter och ta bort hörn och kanter. Hadwiger-talet är också känt som numret på klicksammandragningen av grafen G [1] eller graden av homomorfism av grafen G [2] . Numret är uppkallat efter Hugo Hadwiger , som introducerade numret 1943 och antog att Hadwiger-numret alltid är åtminstone det kromatiska numret på grafen G.
Grafer med ett Hadwiger-nummer på 4 eller mindre beskrivs av Wagner [3] . Grafer med valfritt ändligt Hadwiger-tal är glesa och har ett litet kromatiskt tal. Att bestämma Hadwiger-talet för en graf är NP-svårt , men problemet är lösbart med fasta parametrar.
En graf G har ett Hadwiger-tal som högst 2 om och bara om det är en skog och en trevertex komplett moll kan bildas genom att kontrahera en cykel i G .
En graf har ett Hadwiger-tal på tre eller mindre om och endast om dess trädbredd inte överstiger två, vilket gäller om och endast om något av dess gångjärn är en parallell-seriell graf .
Av Wagners sats , som beskriver plana grafer med sina förbjudna subgrafer , följer att plana grafer har ett Hadwiger-tal som inte överstiger 4. I vissa artiklar som innehåller beviset för satsen beskriver Wagner [3] grafer med ett Hadwiger-tal på fyra eller mindre mer exakt - det här är grafer, som kan bildas med hjälp av summa-för-klick- operationer av plana grafer med en Wagner-graf med 8 hörn.
Grafer med ett Hadwiger-tal mindre än fem inkluderar vertexgrafer och länkfria inbäddningsbara grafer , båda familjerna har en komplett graf K 6 bland förbjudna minderåriga [4]
Varje graf med n hörn och Hadwiger nummer k har O( nk √ log k ) kanter. Denna gräns är exakt — för vilken k som helst finns det en graf med Hadwiger nummer k som har Ω( nk √ log k ) kanter [5] [6] [7] . Om en graf G har ett Hadwiger-tal k , så har alla dess subgrafer också ett Hadwiger-tal som högst k , och detta innebär att grafen G måste ha degeneration O( k √ log k ). Sålunda är grafer med ett begränsat Hadwiger-tal glesa grafer .
Hadwiger-förmodan säger att Hadwiger-talet alltid är åtminstone det kromatiska numret på grafen G. Det vill säga att varje graf med ett Hadwiger-tal k bör ha en färgning med högst k färger. Fallet k = 4 är ekvivalent (genom Wagners karakterisering av grafer med detta Hadwiger -nummer) med fyrfärgsproblemet med att färglägga plana grafer . Hypotesen har också bevisats för k ≤ 5, men förblir obevisad för stora värden på k [8]
På grund av den låga densiteten kan grafer med ett Hadwiger-tal som inte överstiger k färgas med den giriga färgalgoritmen i O( k √ log k ) färger.
Att kontrollera om Hadwiger-talet för en given graf är större än något värde k är ett NP-komplett problem [9] , vilket innebär att bestämning av Hadwiger-talet är ett NP-hårt problem . Problemet är dock fast-parametriskt lösbart — det finns en algoritm för att bestämma den största klick-minor i tiden, beroende endast polynomiellt på storleken på grafen, men exponentiellt på h ( G ) [10] . Dessutom kan polynomtidsalgoritmer approximera Hadwiger-talet mycket mer exakt än den bästa polynomtidsapproximationen (förutsatt att P ≠ NP) av storleken på de största kompletta subgraferna [10] .
Det akromatiska numret för en graf G är storleken på den största klick som kan bildas genom att sammandra en familj av oberoende uppsättningar i G .
Oräkneliga klick minderåriga i oändliga grafer kan karakteriseras i termer av skyddsrum , som formaliserar undanflyktsstrategier för vissa jakt-undvikande spel - om Hadwiger-talet är oräkneligt, är det lika med ordningen för det största skyddet i grafen [11] .
Varje graf med Hadwiger nummer k har högst n 2 O( k log log k ) klickar (fullständiga subgrafer) [12] .
Halin [2] definierade en klass av grafparametrar, som han kallade S - funktioner. Bland dem finns Hadwiger-numret. Dessa funktioner som kartlägger grafer till heltal krävs för att ta noll på kantlösa grafer , vara mindre monotona , öka med ett när man lägger till en ny vertex intill alla tidigare hörn, och från två värden för subgrafer på båda sidor av klickseparatorn bör få ett större värde. Uppsättningen av sådana funktioner bildar ett komplett gittergenom operationer att ta minimi- eller maximumelementen. Det nedre elementet i ett sådant gitter är Hadwiger-numret, och det översta elementet är trädbredden .