T-färgning

En T-färgning av en graf som ges av en uppsättning T av icke-negativa heltal som innehåller 0 är en funktion som mappar varje vertex av G till ett positivt heltal ( färg ) så att [1] . Enkelt uttryckt får det absoluta värdet av skillnaden mellan två färger av intilliggande hörn inte tillhöra en fast uppsättning T . Konceptet föreslogs av William K. Hale [2] . Om T = {0} kokar detta ner till normal vertexfärgning.

Komplementärfärgningen av en T -färgning c , som betecknas som , definieras för varje vertex v i grafen G as , där s är det största antalet färger som tilldelats toppunkten på grafen G av funktionen c [1] .

T -kromatiskt tal

Det T-kromatiska talet är antalet färger som kan användas för att T -färga grafen G . T -kromatiskt tal är lika med kromatiskt tal, [3] .

Bevis

Varje T -färgning av G är också en vertexfärgning av G så att . Låt oss anta det och .

Givet en k-färgningsfunktion av hörn med in i färgerna 1, 2,..,k.

Vi definierar hur

.

För två angränsande hörn u och w i grafen G

,

så .

Sålunda är d en T -färgning av G . Eftersom d använder k färger, .

Därför ■

T -span

För en T -färgning c av en graf G , är c ​​intervallet över alla V(G).

T -spann för grafen G är alla färger c av grafen G [4]

Några T-span gränser anges nedan:

För valfri k-färgning av en graf G med en klick av storlek och valfri ändlig uppsättning T av icke-negativa heltal som innehåller 0, .

För alla grafer G och alla ändliga mängder T av icke-negativa heltal som innehåller 0 vars största element är r , , [5] . För alla grafer G och alla ändliga mängder T av icke-negativa heltal som innehåller 0 av kardinalitet t, . [5] .

Anteckningar

  1. ↑ 1 2 Chartrand, Zhang, 2009 , sid. 397–402.
  2. ↑ Hale, 1980 , sid. 1497–1514
  3. ↑ Cozzens och Roberts 1982 , sid. 191–208.
  4. ↑ Chartrand, Zhang, 2009 , sid. 399.
  5. ↑ 1 2 Cozzens och Roberts, 1982 , sid. 191–208.

Litteratur