Colorare totală

În teoria grafurilor, o colorare totală este un tip de colorare a vârfurilor și a muchiilor unui graf. Cu excepția cazului în care se specifică în mod explicit altfel, se presupune că o colorare totală este corectă , în sensul că niciun vârf adiacent și nicio margine adiacentă și vârfurile aflate la capetele muchiilor nu sunt colorate cu aceeași culoare.

Numărul cromatic total χ″( G ) al unui grafic G este cel mai mic număr de culori necesare pentru o colorare totală a lui G .

Un grafic total T = T( G ) al unui grafic G este un grafic în care

  1. mulţimea vârfurilor graficului T corespunde vârfurilor şi muchiilor graficului G ;
  2. două vârfuri din T sunt adiacente dacă și numai dacă elementele corespunzătoare sunt fie adiacente în G , fie incidente.

Cu această definiție, o colorare totală devine o colorare a vârfurilor (corespunzătoare) a unui grafic total.

Mai multe proprietăți ale lui χ″( G ):

  1. χ″( G ) ≥ Δ( G ) + 1.
  2. χ″( G ) ≤ Δ( G ) + 10 26 [1] .
  3. χ″( G ) ≤ Δ( G ) + 8 ln 8 (Δ( G )) pentru Δ( G ) [2] suficient de mare .
  4. χ″( G ) ≤ ch′( G ) + 2.

Aici Δ( G ) este puterea maximă a lui , iar ch′( G ) este indicele colorării muchiilor prescrise .

Colorarea totală apare într-un mod natural, deoarece este un amestec simplu de coloranți de vârf și margini. Următorul pas este să luăm în considerare limitele superioare ale numărului cromatic total în termeni de gradul maxim, prin analogie cu teoremele Brooks sau Vizing . S-a dovedit că determinarea limitelor superioare ale unei colorări totale în funcție de gradul maxim este o sarcină dificilă și a eludat matematicienilor timp de 40 de ani.

Cea mai faimoasă presupunere este așa:

Conjectura despre colorarea totală.

χ″( G ) ≤ Δ( G ) + 2.

Aparent, termenul „colorare totală” și formularea conjecturii au fost propuse independent de Behzad și Vizing în numeroase publicații între 1964 și 1968 (a se vedea cartea lui Jensen și Toft [3] pentru detalii).

Se știe că conjectura este valabilă pentru mai multe clase importante de grafuri, cum ar fi grafurile bipartite și majoritatea grafurilor plane , cu excepția grafurilor cu un grad maxim de 6. Cazul grafurilor plane va fi rezolvat dacă conjectura grafului plan a lui Vizing este s-a dovedit a fi adevărat. De asemenea, dacă presupunerea despre colorarea muchiilor prescrisă este adevărată, atunci χ″( G ) ≤ Δ( G ) + 3.

S-au obţinut câteva rezultate privind colorarea totală. De exemplu, Kylakos și Read [4] au demonstrat că indicele cromatic fracționar al graficului total pentru un grafic G nu depășește Δ( G ) + 2.

Menționăm, de asemenea, următoarea legătură între graficul cu linii și graficul total :

T ( G ) este Euler dacă și numai dacă L ( G ) este Euler .

Note

  1. ↑ Molloy, Reed, 1998 .
  2. ↑ Hind, Molloy, Reed, 1998 .
  3. ↑ Jensen, Toft, 1995 .
  4. ↑ Kilakos, Reed, 1993 .

Literatură