Hajós konstruktion

Inom grafteorin , en gren av matematiken, är Hajós-konstruktionen en operation på grafer uppkallade efter György Hajós ( 1961 ) som kan användas för att konstruera vilken kritisk graf som helst eller vilken graf som helst vars kromatiska tal är åtminstone någon given tröskel.

Konstruktionen

Tillämpa Hajós-konstruktionen på två kopior av K ₄ genom att identifiera en vertex från varje kopia till en enda vertex (visas med båda färgerna), ta bort en kant som faller in på den kombinerade vertexen inom varje subgraf (streckad) och lägga till en ny kant som förbinder ändpunkterna av de raderade kanterna (tjockgröna), producerar Moser-spindeln .

Låt G och H vara två oriktade grafer , vw vara en kant av G , och xy vara en kant av H. Sedan bildar Hajós-konstruktionen en ny graf som kombinerar de två graferna genom att identifiera hörn v och x till en enda vertex, ta bort de två kanterna vw och xy och lägga till en ny kant wy .

Låt till exempel G och H vara en komplett graf K ₄ på fyra hörn; på grund av symmetrin i dessa grafer är valet av vilken kant som ska väljas från var och en av dem oviktigt. I det här fallet är resultatet av att applicera Hajós-konstruktionen Moser-spindeln , en avståndsgraf med sju vertexenheter som kräver fyra färger.

Som ett annat exempel, om G och H är cykelgrafer med längden p respektive q , så är resultatet av att tillämpa Hajós-konstruktionen i sig en cykelgraf med längden p + q − 1 .

Konstruerbara grafer

En graf G sägs vara k - konstruerbar (eller Hajósk - konstruerbar) när den bildades på något av följande tre sätt:

• Den fullständiga grafen K _k är k -konstruerbar.
• Låt G och H vara vilka två k- konstruerbara grafer som helst. Då är grafen som bildas genom att tillämpa Hajós-konstruktionen på G och H k -konstruerbar .
• Låt G vara vilken k -konstruerbar graf som helst, och låt u och v vara vilken som helst två icke-angränsande hörn i G . Då är grafen som bildas genom att kombinera u och v till en enda vertex också k -konstruerbar. På motsvarande sätt kan denna graf bildas genom att addera kant- uv till grafen och sedan dra ihop den.

Anslutning till färgläggning

Det är enkelt att verifiera att varje k -konstruerbar graf kräver minst k färger i någon korrekt graffärgning . Detta är faktiskt tydligt för hela grafen K _k , och effekten av att identifiera två icke-angränsande hörn är att tvinga dem att ha samma färg som varandra i vilken färg som helst, något som inte minskar antalet färger. I själva Hajós-konstruktionen tvingar den nya kanten wy minst en av de två hörnen w och y att ha en annan färg än den kombinerade vertexen för v och x , så all korrekt färgning av den kombinerade grafen leder till en korrekt färgning av en av de två mindre graferna som den bildades av, vilket återigen gör att den kräver k färger.

Hajós bevisade starkare att en graf kräver minst k färger, i valfri färg , om och bara om den innehåller en k -konstruerbar graf som en subgraf. På motsvarande sätt är varje k - kritisk graf (en graf som kräver k färger men för vilken varje korrekt subgraf kräver färre färger) k -konstruerbar. Alternativt kan varje graf som kräver k färger bildas genom att kombinera Hajós-konstruktionen, operationen att identifiera två icke intilliggande hörn och operationerna att lägga till en vertex eller kant till den givna grafen, med start från hela grafen K _k .

En liknande konstruktion kan användas för listfärgning i stället för färgning.

Konstruerbarhet av kritiska grafer

För k = 3 kan varje k -kritisk graf (det vill säga varje udda cykel) genereras som en k -konstruerbar graf så att alla grafer som bildas i dess konstruktion också är k -kritiska. För k = 8 är detta inte sant: en graf som Catlin (1979) hittat som ett motexempel till Hajós' gissning att k -kromatiska grafer innehåller en underavdelning av K _k , fungerar också som ett motexempel till detta problem. Därefter hittades k -kritiska men inte k- konstruerbara grafer enbart genom k -kritiska grafer för alla k ≥ 4 . För k = 4 är ett sådant exempel grafen som erhålls från dodekaedergrafen genom att lägga till en ny kant mellan varje par av antipodala hörn

Hajós-numret

Eftersom sammanslagning av två icke-intilliggande hörn minskar antalet hörn i den resulterande grafen, kan antalet operationer som krävs för att representera en given graf G med de operationer som definieras av Hajós överstiga antalet hörn i G .

Mer specifikt definierar Mansfield & Welsh (1982) Hajós-talet h ( G ) för en k -kromatisk graf G som det minsta antalet steg som behövs för att konstruera G från K _k , där varje steg bildar en ny graf genom att kombinera två tidigare bildade grafer, sammanslagning av två icke intilliggande hörn av en tidigare bildad graf, eller lägga till en vertex eller kant till en tidigare bildad graf. De visade att för en n -vertexgraf G med m kanter, h ( G ) ≤ 2 ^{n 2 /3 − m + 1} − 1 . Om varje graf har ett polynom Hajós-tal, skulle detta innebära att det är möjligt att bevisa icke-färgbarhet i icke-deterministisk polynomtid, och därför antyda att NP = co-NP , en slutsats som anses osannolik av komplexitetsteoretiker. Det är dock inte känt hur man bevisar icke-polynomiska nedre gränser på Hajós-talet utan att göra något komplexitetsteoretiskt antagande, och om en sådan gräns kunde bevisas skulle det också innebära förekomsten av icke-polynomiska gränser på vissa typer av Frege system i matematisk logik .

Minimistorleken på ett uttrycksträd som beskriver en Hajós-konstruktion för en given graf G kan vara betydligt större än Hajós-talet för G , eftersom ett kortaste uttryck för G kan återanvända samma grafer flera gånger, en ekonomi som inte är tillåten i ett uttryck träd. Det finns 3-kromatiska grafer för vilka det minsta uttrycksträdet har exponentiell storlek.

Andra applikationer

Koester (1991) använde Hajós-konstruktionen för att generera en oändlig uppsättning av 4-kritiska polyedriska grafer , var och en med mer än dubbelt så många kanter som hörn. På liknande sätt Liu & Zhang (2006) konstruktionen, som började med Grötzsch-grafen , för att generera många 4-kritiska triangelfria grafer , som de visade vara svåra att färglägga med traditionella backtracking -algoritmer.

I polyedrisk kombinatorik använde Euler (2003) Hajós-konstruktionen för att generera fasetter av den stabila uppsättningspolytopen .

Anteckningar

• Catlin, PA (1979), "Hajós's graph-colouring conjecture: variations and counterexamples", Journal of Combinatorial Theory , Series B, 26 : 268–274, doi : 10.1016/0095-8956(79)90062-5 .
•   Diestel, Reinhard (2006), Graph Theory , Graduate Texts in Mathematics, vol. 173 (3:e uppl.), Springer-Verlag, s. 117–118, ISBN 978-3-540-26183-4 .
•   Euler, Reinhardt (2003), "Hajós' konstruktion och polytoper", Kombinatorisk optimering — Eureka, du krymper! , Lecture Notes in Computer Science, vol. 2570, Berlin: Springer-Verlag, s. 39–47, doi : 10.1007/3-540-36478-1_6 , MR 2163949 .
•   Gravier, Sylvain (1996), "A Hajós-like theorem for list coloring", Discrete Mathematics , 152 (1–3): 299–302, doi : 10.1016/0012-365X(95)00350-6 , MR 50 13886 .
• Hajós, G. (1961), "Über eine Konstruktion nicht n -färbbarer Graphen", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe , 10 : 116–117 . Som citeras av Jensen & Toft (1994) .
•   Iwama, Kazuo ; Pitassi, Toniann (1995), "Exponential lower bounds for the tree-like Hajós calculus", Information Processing Letters , 54 (5): 289–294, doi : 10.1016/0020-0190(95)00035-B , MR 33601 .
•   Jensen, Tommy R.; Royle, Gordon F. (1999), "Hajós constructions of critical graphs", Journal of Graph Theory , 30 (1): 37–50, doi : 10.1002/(SICI)1097-0118(199901)30:1<37: :AID-JGT5>3.0.CO;2-V , MR 1658542 .
•   Jensen, Tommy R.; Toft, Bjarne (1994), Graph Coloring Problems (2nd ed.), John Wiley and Sons, ISBN 978-0-471-02865-9 .
•   Koester, Gerhard (1991), "On 4-critical planar graphs with high edge density", Discrete Mathematics , 98 (2): 147–151, doi : 10.1016/0012-365X(91)90039-5 , MR 3 1144633 .
•   Kubale, Marek (2004), Graph Colorings , Contemporary Mathematics, vol. 352, American Mathematical Society, sid. 156, ISBN 978-0-8218-3458-9 .
• Liu, Sheng; Zhang, Jian (2006), "Using Hajós' konstruktion för att generera hårda grafer med 3-färgbarhetsinstanser", Artificiell intelligens och symbolisk beräkning , Lecture Notes in Computer Science, vol. 4120, Springer-Verlag, s. 211–225, doi : 10.1007/11856290_19 .
•   Mansfield, AJ; Welsh, DJA (1982), "Some coloring problems and their complexity", Graph theory (Cambridge, 1981) , North-Holland Math. Stud., vol. 62, Amsterdam: North-Holland, s. 159–170, MR 0671913 .
•    Pitassi, Toniann ; Urquhart, Alasdair (1995), "The Complexity of Hajós Calculus", Siam Journal om diskret matematik , 8 (3): 464–483, Citeseerx 10.1.1.30.5879 , doi : 10.1137/s08954801924024x , MR 1341550 .