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

Given a graph G   and p∈Np∈N, a proper n  -[p][p]coloring is a mapping f:V(G)→2{1,…,n}f:V(G)→2{1,…,n} such that |f(v)|=p|f(v)|=p for any vertex v∈V(G)v∈V(G) and f(v)∩f(u)=∅f(v)∩f(u)=∅ for any pair of adjacent vertices u and v. An n  -[p][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 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.

► Multicoloring of triangle-free hexagonal graphs is discussed.
► Linear time algorithm for 7-[3]coloring of triangle-free hexagonal graph is provided.
► An extension to a proper multicoloring with at most ⌈7/6ωm(G)⌉+O(1)⌈7/6ωm(G)⌉+O(1) colors is possible.