A linear time algorithm for 7-[3]coloring triangle-free hexagonal graphs

Given a graph G and p is an element of N, a proper n-[p]coloring is a mapping f : V (G) -> 2((1....,n)) such that vertical bar f(v)vertical bar = p for any vertex v is an element of V (G) and f(v) boolean AND (u) = (sic) 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-free hexagonal graphs in linear time, without using the fourcolor theorem, which solves the open problem stated by Sau. Snarl and Zerovnik (2011) and improves the result of Sudeep and Vishwanathan (2005), who proved the existence of a 14-[6]coloring. (C) 2012 Elsevier B.V. All rights reserved.