Simpler multicoloring of triangle-free hexagonal graphs

Given a graph G and a demand function p: V(G) -> N, a proper n-[p]coloring is a mapping f : V(G) -> 2([1.....n]) such that vertical bar f (v)vertical bar >= p(v) for every vertex v epsilon V(G) and f(v) boolean AND 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 multichrornatic 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) [8] conjectured that chi(p)(G) <= (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 epsilon V (G)), which implies that chi(p)(G) <= (7/6)omega(p)(G) + C. Our result constitutes a shorter alternative to the inductive proof of Havet (2001) [5] and improves the short proof of Sudeep and Vishwanathan (2005) [17], 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 vertical bar V(G)vertical bar, 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) [8]. (C) 2011 Elsevier B.V. All rights reserved.