Ignasi Sau Walls (Avtor), Petra Šparl (Avtor), Janez Žerovnik (Avtor)

Povzetek

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;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.08 - Objavljeni znanstveni prispevek na konferenci
Organizacija: UL FS - Fakulteta za strojništvo
UDK: 519.17
COBISS: 6917907 Povezava se bo odprla v novem oknu
ISSN: 0012-365X
Št. ogledov: 797
Št. prenosov: 72
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Enostavnejše večbarvanje heksagonalnih grafov brez trikotnikov
Sekundarni povzetek: 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).
URN: URN:SI:UM:
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: Str. 181-187
Letnik: ǂVol. ǂ312
Zvezek: ǂiss. ǂ1
Čas izdaje: 2012
ID: 1471875