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 | f ( v ) | ≥ p ( v ) for every vertex v ∈ V ( G ) and f ( v ) ∩ f ( u ) = 0̸ for any two adjacent vertices u and v . The least integer n for which a proper n -[ p ]coloring exists, χ 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 , ω 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 χ p ( G ) ≤ ( 9 / 8 ) ω 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 ∈ V ( G ) ), which implies that χ p ( G ) ≤ ( 7 / 6 ) ω 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 | 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) [8].