Irreducibility of L(2,1)-colorings and the inh-colorability of unicyclic and hex graphs
Abstract
The channel assignment problem is the problem of as-signing radio frequencies to transmitters while avoiding interference. This problem can be modeled and examined using graphs and graph colorings. Griggs and Yeh first studied L(2,1)-colorings as a model of a variation of the channel assignment problem proposed by Roberts. The span of a graph, G, is the smallest integer λ such that there exists an L(2,1)-coloring using the integers {0,1,..., λ} on G. A no-hole coloring is defined to be an L(2,1)-coloring of a graph which uses all the colors from {0,1,..., k} for some integer k. An L(2,1)-coloring is irreducible if no colors of vertices in the graph can be decreased and yield another L(2,1)-coloring. A graph G is inh-colorable if there exists an irreducible no-hole coloring on G. In this paper we examine the irreducible property and its relationship to the span. We discuss unicyclic and hex graphs and show that these classes of graphs are inh-colorable. For unicyclic graphs the proof of inh-colorability will provide fairly tight bounds for the lower inh-span. The algorithm for coloring the hex graphs will provide an upper bound for the lower inh-span of the hex graph.
