Total färg - Total coloring

Korrekt totalfärgning av Fosterbur med 6 färger. Det totala kromatiska antalet i denna graf är 6 eftersom graden för varje toppunkt är 5 (5 intilliggande kanter + 1 topp = 6).

I grafteori , totala mängden färgämnen är en typ av algoritmer för sortering på vertex och kanter av en graf. När den används utan någon kvalifikation antas en total färgning alltid vara korrekt i den meningen att inga intilliggande kanter, inga intilliggande hörn och ingen kant och endera endvertex tilldelas samma färg. Den totala kromatiska antalet χ "( G ) för en graf G är det minsta antalet färger som behövs i alla totala färgning av G .

Den totala grafen T = T ( G ) för en graf G är en graf så att (i) toppuppsättningen av T motsvarar topparna och kanterna på G och (ii) två vertikaler angränsar i T om och endast om deras motsvarande element är antingen intill eller incident i G . Då blir total färgning av G en (korrekt) toppfärgning av T ( G ). En total färgning är en uppdelning av kurvorna och kanterna i diagrammet i totala oberoende uppsättningar .

Några ojämlikheter för χ ″ ( G ):

1. χ ″ ( G ) ≥ Δ ( G ) + 1.
2. χ ″ ( G ) ≤ Δ ( G ) + 10 ²⁶ . (Molloy, Reed 1998)
3. χ ″ ( G ) ≤ Δ ( G ) + 8 ln ⁸ (Δ ( G )) för tillräckligt stor Δ ( G ). (Hind, Molloy, Reed 1998)
4. χ ″ ( G ) ≤ ch ′ ( G ) + 2.

Här är Δ ( G ) den maximala graden ; och ch ′ ( G ), kantvalet .

Total färgning uppstår naturligt eftersom det helt enkelt är en blandning av topp- och kantfärgningar. Nästa steg är att leta efter någon Brooks- typad eller Vizing- typ övre gräns på det totala kromatiska antalet i termer av maximal grad.

Den totala färgversionen av den övre gränsen för maximal grad är ett svårt problem som har undgått matematiker i 50 år. En trivial nedre gräns för χ ″ ( G ) är Δ ( G ) + 1. Vissa grafer som längdcykler och fullständiga tvådelade diagram av formen behöver Δ ( G ) + 2 färger men ingen graf har hittats som kräver fler färger . Detta leder till spekulationer om att varje graf behöver antingen Δ ( G ) + 1 eller Δ ( G ) + 2 färger, men aldrig mer: ${\ displaystyle n \ not \ equiv 0 {\ bmod {3}}}$${\ displaystyle K_ {n, n}}$

Total färggissning ( Behzad , Vizing).${\ displaystyle \ chi '' (G) \ leq \ Delta (G) +2.}$

Uppenbarligen introducerades termen "total färgning" och uttalandet om total färggissning oberoende av Behzad och Vizing vid flera tillfällen mellan 1964 och 1968 (se Jensen & Toft). Antagandet är känt för att innehålla några viktiga klasser av grafer, såsom alla bipartitgrafer och de flesta plana grafer utom de med maximal grad 6. Det plana fallet kan slutföras om Vizings plana grafgissningar är sanna. Också, om listans färggissningar är sanna, då${\ displaystyle \ chi '' (G) \ leq \ Delta (G) +3.}$

Resultat relaterade till total färg har erhållits. Exempelvis bevisade Kilakos och Reed (1993) att det fraktionerade kromatiska antalet för den totala grafen i en graf G är högst Δ ( G ) + 2.

Referenser

• Hind, Hugh; Molloy, Michael; Reed, Bruce (1998). "Total färgning med Δ + poly (log Δ) färger". SIAM Journal on Computing . 28 (3): 816–821. doi : 10.1137 / S0097539795294578 .
• Jensen, Tommy R .; Toft, Bjarne (1995). Problem med graffärgning . New York: Wiley-Interscience. ISBN  0-471-02865-7 .
• Kilakos, Kyriakos; Reed, Bruce (1993). "Fraktionellt färglägga totala grafer". Combinatorica . 13 (4): 435–440. doi : 10.1007 / BF01303515 .
• Molloy, Michael; Reed, Bruce (1998). "En gräns för det totala kromatiska antalet". Combinatorica . 18 (2): 241–280. doi : 10.1007 / PL00009820 . hdl : 1807/9465 .