Petra Šparl (Author), Rafał Witkowski (Author), Janez Žerovnik (Author)

Abstract

Given a graph ▫$G$▫ and ▫$p \in \mathbb{N}$▫, a proper ▫$n-[p]$▫coloring is a mapping ▫$f \colon V(G) \to 2^{\{1,dots,n\}}$▫ such that ▫$|f(v)| = p$▫ for any vertex ▫$v \in V(G)$▫ and ▫$f(v) \cap f(u) = \emptyset$▫ for any pair of adjacent vertices ▫$u$▫ and ▫$v$▫. An ▫$n-[p]$▫coloring is a special case of a multicoloring. Finding a multicoloring of induced subgraphs of the triangular lattice (called hexagonal graphs) has important applications in cellular networks. In this article we provide an algorithm to find a ▫$7-[3]$▫coloring of triangle-freehexagonal graphs in linear time, without using the four-color theorem, which solves the open problem stated by Sau, Šparl and Žerovnik (2011) and improves the result of Sudeep and Vishwanathan (2005), who proved the existence of a ▫$14-[6]$▫coloring.

Keywords

aproksimacijski algoritem;večbarvanje;dodeljevanje frekvenc;heksagonalen graf;approximation algorithm;multicoloring;frequency planning;hexagonal graph;

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UL FS - Faculty of Mechanical Engineering
UDC: 519.174
COBISS: 7018003 Link will open in a new window
ISSN: 0020-0190
Views: 1214
Downloads: 100
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary keywords: aproksimacijski algoritem;večbarvanje;dodeljevanje frekvenc;heksagonalen graf;
URN: URN:SI:UM:
Pages: str. 567-571
Volume: ǂVol. ǂ112
Issue: ǂiss. ǂ14-15
Chronology: 2012
ID: 8723553