VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Simpler multicoloring of triangle-free hexagonal graphs
    Sau Walls, Ignasi ; Šparl, Petra, 1975-2016 ; Žerovnik, Janez, 1958-
    Preslikavo ▫$f \colon V(G)\to 2^{\{1,.,n\}}$▫, za katero velja ▫$|f(v)| \ge p(v)$▫ za vsako točko ▫$v \in V(G)$▫ in ▫$f(v) \cap f(u) = \emptyset$▫ za poljubni sosedi ▫$u$▫ in ▫$v$▫ grafa ▫$G$▫, ... imenujemo dobro ▫$n-[p]$▫barvanje grafa ▫$G$▫. Najmanjše naravno število, za katero obstaja dobro ▫$n-[p]$▫barvanje grafa ▫$G$▫, ▫$\chi_p(G)$▫, imenujemo uteženo kromatično število grafa ▫$G$▫. Iskanje uteženega kromatičnega števila za inducirane podgrafe trikotniške mreže (imenovane heksagonalni grafi) ima aplikacije v celičnih mrežah. Uteženo kromatično število grafa ▫$G$▫, ▫$\omega_p(G)$▫, je enako maksimalni uteži klike grafa ▫$G$▫, kjer utež klike predstavlja vsoto uteži njenih točk. McDiarmid in Reed (2000) sta postavila domnevo, da za poljuben heksagonalen graf brez trikotnikov velja ▫$\chi_p(G) \le (9/8)\omega_p(G) + C$▫. V članku je podan algoritem, ki poda dobro ▫$7-[3]$▫barvanje poljubnega heksagonalnega grafa brez trikotnikov, ki aplicira neenakost ▫$\chi_p(G) \le (7/6)\omega_p(G) + C$▫. Naš rezultat podaja krajšo alternativo induktivnega dokaza Haveta (2001) in izboljša kratek dokaz Sudepa in Vishwanathana (2005), ki sta dokazala obstoj ▫$14-[6]$▫barvanja. (Omeniti je potrebno, da v sklopu našega dokaza uporabimo izrek o štirih barvah.) Vsi koraki algoritma so linearni glede na ▫$|V(G)|$▫, razen 4-barvanje ravninskega grafa. Novi pristop lahko v prihodnje pripomore k dokazovanju domneve McDiarmida in Reeda (2000).
    Vir: Algebraic graph theory : a volume dedicated to Gert Sabidussi on the occasion of his 80th birthday (Vol. 312, iss. 1, 2012, Str. 181-187)
    Vrsta gradiva - prispevek na konferenci ; neleposlovje za odrasle
    Leto - 2012
    Jezik - angleški
    COBISS.SI-ID - 6917907

    Povezava(-e):

    http://dx.doi.org/10.1016/j.disc.2011.07.031
    Digitalna knjižnica Univerze v Mariboru – DKUM

Vnos na polico