| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:Simpler multicoloring of triangle-free hexagonal graphs
Avtorji:Sau Walls, Ignasi (Avtor)
Šparl, Petra (Avtor)
Žerovnik, Janez (Avtor)
Datoteke:URL http://dx.doi.org/10.1016/j.disc.2011.07.031
 
Jezik:Angleški jezik
Vrsta gradiva:Delo ni kategorizirano (r6)
Tipologija:1.08 - Objavljeni znanstveni prispevek na konferenci
Organizacija:FOV - Fakulteta za organizacijske vede
Opis: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).
Ključne besede:matematika, teorija grafov, aproksimacijski algoritem, barvanje grafov, dodeljevanje frekvenc, celične mreže, mathematics, graph algorithm, graph theory, approximation algorithm, graph coloring, frequency planning, cellular networks
Leto izida:2012
Št. strani:Str. 181-187
Številčenje:Vol. 312, iss. 1
UDK:519.17
COBISS_ID:6917907 Povezava se odpre v novem oknu
ISSN pri članku:0012-365X
NUK URN:URN:SI:UM:DK:IOFJJWSU
Število ogledov:443
Število prenosov:51
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
Področja:Ostalo
:
  
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del zbornika

Naslov:Algebraic graph theory
COBISS.SI-ID:16067161 Novo okno

Gradivo je del revije

Naslov:Discrete Mathematics
Skrajšan naslov:Discrete math.
Založnik:North-Holland
ISSN:0012-365X
COBISS.SI-ID:1118479 Novo okno

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Enostavnejše večbarvanje heksagonalnih grafov brez trikotnikov
Opis:Given a graph ▫$G$▫ and a demand function ▫$p colon V(G)to mathbb{N}$▫, a proper ▫$n-[p]$▫coloring is a mapping ▫$f colon V(G)to 2^{{1,.,n}}$▫ such that ▫$|f(v)| ge p(v)$▫ for every vertex ▫$v in V(G)$▫ and ▫$f(v) cap f(u) = emptyset$▫ for any two adjacent vertices ▫$u$▫ and ▫$v$▫. The least integer ▫$n$▫ for which a proper ▫$n-[p]$▫coloring exists, ▫$chi_p(G)$▫, is called multichromatic number of ▫$G$▫. Finding multichromatic number of induced subgraphs of the triangular lattice (called hexagonal graphs) has applications in cellular networks. Weighted clique number of a graph ▫$G$▫, ▫$omega_p(G)$▫, is the maximum weight of a clique in ▫$G$▫, where the weight of a clique is the total demand of its vertices. McDiarmid and Reed (2000) conjectured that ▫$chi_p(G) le (9/8)omega_p(G)+C$▫ for triangle-free hexagonal graphs, where ▫$C$▫ is some absolute constant. In this article, we provide an algorithm to find a ▫$7-[3]$▫coloring of triangle-free hexagonal graphs (that is, when ▫$p(v) = 3$▫ for all ▫$v in V(G)$▫), which implies that ▫$chi_p(G) le (7/6)omega_p(G) + C$▫. Our result constitutes a shorter alternative to the inductive proof of Havet (2001) and improves the short proof of Sudeep and Vishwanathan (2005), who proved the existence of a ▫$14-[6]$▫coloring. (It has to be noted, however, that our proof makes use of the 4-color theorem.) All steps of our algorithm take time linear in ▫$|V(G)|$▫, except for the 4-coloring of an auxiliary planar graph. The new techniques may shed some light on the conjecture of McDiarmid and Reed (2000).


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici