Hadwiger-nummer - Hadwiger number
I grafteori , den Hadwiger antalet av en oriktad graf G är storleken på den största komplett graf som kan erhållas genom avtals kanter av G . Ekvivalent, den Hadwiger nummer h ( G är) det största antalet k för vilket den fullständiga grafen K k är en liten av G , en mindre graf erhållen från G genom kant sammandragningar och vertex och kant deletioner. Den Hadwiger nummer är också känd som den kontraktion klick antal av G eller homomorfism graden av G . Den är uppkallad efter Hugo Hadwiger , som introducerade den 1943 i samband med Hadwiger gissningar , som anger att Hadwiger antalet är alltid minst lika stor som den kromatiska antal av G .
Graferna som har Hadwiger-talet högst fyra har karaktäriserats av Wagner (1937) . Diagrammen med någon begränsad gräns på Hadwiger-talet är glesa och har litet kromatiskt tal. Bestämning av Hadwiger-numret i en graf är NP-hård men fast-parameter kan hanteras .
Grafer med litet Hadwiger-nummer
En graf G har Hadwiger antal högst två om och endast om det är en skog , för en tre-vertex komplett mindre kan endast bildas genom contracting en cykel i G .
En graf har Hadwiger-talet högst tre om och bara om dess trebredd är högst två, vilket är sant om och endast om var och en av dess tvåanslutna komponenter är en serie-parallell graf .
Wagners sats , som karakteriserar de plana graferna av deras förbjudna minderåriga , antyder att de plana graferna har högst fyra Hadwiger-nummer. I samma papper som bevisade denna teorem karakteriserade Wagner (1937) också graferna med Hadwiger-talet högst fyra mer exakt: de är grafer som kan bildas av klicksummoperationer som kombinerar plana grafer med Wagner-grafen med åtta topparna .
Diagrammen med högst fem Hadwiger-nummer inkluderar toppdiagrammen och de länklöst inbäddade graferna , som båda har den fullständiga grafen K 6 bland sina förbjudna minderåriga.
Gleshet
Varje graf med n hörn och Hadwiger-tal k har O ( nk √ log k ) kanter. Denna gräns är tät: för varje k finns det grafer med Hadwiger-tal k som har Ω ( nk √ log k ) kanter. Om en graf G har Hadwiger-tal k , har alla dess underbilder också högst Hadwiger-nummer k , och det följer att G måste ha degenerering O ( k √ log k ). Därför är graferna med begränsat Hadwiger-nummer glesa diagram .
Färg
Den Hadwiger gissningar anges att Hadwiger antalet är alltid åtminstone lika stor som den kromatiska antal av G . Det vill säga att varje graf med Hadwiger-nummer k ska ha en graffärgning med högst k- färger. Fallet k = 4 är ekvivalent (genom Wagners karaktärisering av graferna med detta Hadwiger-nummer) med fyrfärgssatsen på färgningar av plana grafer , och antagandet har också bevisats för k ≤ 5, men förblir obevisat för större värden av k .
På grund av deras låga degenereringsgrad kan graferna med högst Hadwiger-tal färgas av en girig färgningsalgoritm med O ( k √ log k ) färger.
Beräkningskomplexitet
Att testa om Hadwiger-numret för en given graf är åtminstone ett givet värde k är NP-komplett , varifrån det följer att bestämningen av Hadwiger-talet är NP-hård . Problemet är emellertid fast parametrar som kan spåras : det finns en algoritm för att hitta den största klickmoll på en tid som bara beror polynomiskt på grafens storlek, men exponentiellt i h ( G ). Dessutom kan polynomaltidsalgoritmer approximera Hadwiger-talet betydligt mer exakt än den bästa polynomtidstiden (förutsatt P ≠ NP) till storleken på den största kompletta subgrafen .
Relaterade begrepp
Det akromatiska talet i en graf G är storleken på den största klicken som kan bildas genom att en familj av oberoende uppsättningar i G får kontrakt .
Otalbara klickmindreåriga i oändliga diagram kan karakteriseras i termer av tillflyktsort , som formaliserar undvikelsestrategierna för vissa strävande-undvikelsesspel : om Hadwiger-numret är oräkneligt, är det lika med den största ordningen på en fristad i grafen.
Varje diagram med Hadwiger-nummer k har högst n 2 O ( k logg k ) klick (kompletta underbilder).
Halin (1976) definierar en klass av grafparametrar som han kallar S- funktioner, som inkluderar Hadwiger-numret. Dessa funktioner från grafer till heltal måste vara noll på grafer utan kanter , vara mindre monotone , öka med en när ett nytt toppunkt läggs till som gränsar till alla tidigare hörn och ta det större värdet från de två subgrafer på vardera sidan av en klick separator . Uppsättningen av alla sådana funktioner bildar ett komplett galler under operationerna med elementvis minimering och maximering. Det nedre elementet i detta gitter är Hadwiger-numret och det övre elementet är träbredden .
Anteckningar
Referenser
- Alon, Noga ; Lingor, Andrzej; Wahlen, Martin (2007), "Approximating the maximum clique minor and some subgraph homeomorphism problems" (PDF) , Theoretical Computer Science , 374 (1–3): 149–158, doi : 10.1016 / j.tcs.2006.12.021.
- Bollobás, B .; Catlin, PA; Erdős, Paul (1980), "Hadwigers antagande är sant för nästan varje graf" (PDF) , European Journal of Combinatorics , 1 : 195–199, doi : 10.1016 / s0195-6698 (80) 80001-1.
- Eppstein, David (2009), "Det är svårt att hitta stora klickbarn", Journal of Graph Algorithms and Applications , 13 (2): 197–204, arXiv : 0807.0007 , doi : 10.7155 / jgaa.00183.
- Fomin, Fedor V .; Oum, Sang-il ; Thilikos, Dimitrios M. (2010), " Rankbredd och trädbredd för H- mindre grafer", European Journal of Combinatorics , 31 (7): 1617–1628, arXiv : 0910.0079 , doi : 10.1016 / j. ejc.2010.05.003.
- Hadwiger, Hugo (1943), "Über eine Klassifikation der Streckenkomplexe", Vierteljschr. Naturforsch. Ges. Zürich , 88 : 133–143.
- Halin, Rudolf (1976), " S -funktioner för grafer", J. Geometry , 8 (1–2): 171–186, doi : 10.1007 / BF01917434 , MR 0444522.
- Kostochka, AV (1984), "Nedre gräns för Hadwiger-antalet diagram efter deras genomsnittliga grad", Combinatorica , 4 (4): 307–316, doi : 10.1007 / BF02579141.
- Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1991), "Exklusive oändliga minderåriga", Diskret matematik , 95 (1–3): 303–319, doi : 10.1016 / 0012-365X (91) 90343-Z , MR 1141945.
- Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1993a), "Hadwiger's conjecture for K 6 -free charts" (PDF) , Combinatorica , 13 (3): 279–361, doi : 10.1007 / BF01202354.
- Robertson, Neil ; Seymour, PD ; Thomas, Robin (1993b), "Länklösa inbäddningar av grafer i 3-mellanslag", Bulletin of the American Mathematical Society , 28 (1): 84–89, arXiv : math / 9301216 , doi : 10.1090 / S0273-0979-1993- 00335-5 , MR 1164063.
- Thomason, Andrew (2001), "Extremfunktionen för kompletta minderåriga", Journal of Combinatorial Theory , serie B, 81 (2): 318–338, doi : 10.1006 / jctb.2000.2013.
- Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe", Math. Ann. , 114 : 570–590, doi : 10.1007 / BF01594196.