Enostavnejše večbarvanje heksagonalnih grafov brez trikotnikov

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).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)