Т-бояуы - T-coloring

T = {0, 1, 4} үшін графиктің екі T-түсі

Жылы графтар теориясы, а T-бояу график ${ displaystyle G = (V, E)}$, Берілген орнатылды Т 0 мәні бар теріс емес бүтін сандар функциясы болып табылады ${ displaystyle c: V (G) to mathbb {N}}$ әрбір шыңды оң бүтін санға түсіретін (түс ) егер солай болса сен және w сол кезде іргелес ${ displaystyle | c (u) -c (w) | T емес)$.^[1] Қарапайым сөзбен айтқанда, іргелес шыңдардың екі түсі арасындағы айырмашылықтың абсолюттік мәні бекітілген жиынтыққа жатпауы керек Т. Тұжырымдаманы Уильям К.Хейл ұсынды.^[2] Егер Т = {0} ол шыңның қарапайым түсіне дейін азаяды.

The Т-хроматикалық сан, ${ displaystyle chi _ {T} (G),}$ а-да қолдануға болатын минималды түстер саны Т-бояу G.

The қосымша бояу туралы Т-түстеу в, деп белгіленді ${ displaystyle { overline {c}}}$ әрбір төбе үшін анықталады v туралы G арқылы

${ displaystyle { overline {c}} (v) = s + 1-c (v)}$

қайда с - шыңына тағайындалған ең үлкен түс G бойынша в функциясы.^[1]

Хроматикалық санмен байланыс

Ұсыныс. ${ displaystyle chi _ {T} (G) = chi (G)}$.^[3]

Дәлел. Әрқайсысы Т-бояу G сонымен қатар G, сондықтан ${ displaystyle chi _ {T} (G) geq chi (G).}$ Айталық ${ displaystyle chi (G) = k}$ және ${ displaystyle r = max (T).}$ Жалпы шың берілген к-бояу функциясы ${ displaystyle c: V (G) to mathbb {N}}$ түстерді қолдану ${ displaystyle {1, ldots, k }.}$ Біз анықтаймыз ${ displaystyle d: V (G) to mathbb {N}}$ сияқты

${ displaystyle d (v) = (r + 1) c (v)}$

Әрбір іргелес екі төбеге арналған сен және w туралы G,

${ displaystyle | d (u) -d (w) | = | (r + 1) c (u) - (r + 1) c (w) | = (r + 1) | c (u) -c (d) w) | geq r + 1}$

сондықтан ${ displaystyle | d (u) -d (w) | T. емес)$ Сондықтан г. Бұл Т-бояу G. Бастап г. қолданады к түстер, ${ displaystyle chi _ {T} (G) leq k = chi (G).}$ Демек, ${ displaystyle chi _ {T} (G) = chi (G).}$

Т- аралық

А аралығы Т-түстеу в туралы G ретінде анықталады

${ displaystyle sp_ {T} (c) = max _ {u, w in V (G)} | c (u) -c (w) |.}$

The Т- аралық ретінде анықталады:

${ displaystyle sp_ {T} (G) = min _ {c} sp_ {T} (c).}$^[4]

Кейбір шектері Т-span төменде келтірілген:

• Әрқайсысы үшін к-хроматикалық график G өлшемімен ${ displaystyle omega}$ және барлық ақырлы жиынтық Т құрамында 0 болатын теріс емес бүтін сандар, ${ displaystyle sp_ {T} (K _ { omega}) leq sp_ {T} (G) leq sp_ {T} (K_ {k}).}$

• Әр график үшін G және барлық ақырлы жиынтық Т 0 болатын теріс емес бүтін сандар, олардың ең үлкен элементі р, ${ displaystyle sp_ {T} (G) leq ( chi (G) -1) (r + 1).}$^[5]

• Әр график үшін G және барлық ақырлы жиынтық Т 0 мәні бар теріс емес бүтін сандар т, ${ displaystyle sp_ {T} (G) leq ( chi (G) -1) t.}$ ^[5]

Сондай-ақ қараңыз

• Графикті бояу

Әдебиеттер тізімі