- 209 views
- 46 downloads

In the application area of frequency assignment graphs are used to model the topology and mutual interference between transmitters. The problem in practice is to assign a limited number of frequency channels in aneconomical way to the transmitter in such a way that interference is kept at an acceptable level. This has led to various different types of coloring problem in graphs. One of them is a -backbone coloring. Given an integer 2, a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a -backbone coloring of (G,H) is a proper vertex coloring V ! {1, 2, . . .} of G in which the colors assigned to adjacent vertices in H differ by at least . The -backbone coloring number BBC(G,H) of (G,H) is the smallest integer ` for which there exists a -backbone coloring f : V -> {1, 2, . . . , l}. In this paper we consider the -backbone coloring of split graphs. A split graph is a graph whose vertex set can be partitioned into a clique (i.e. a set of mutually adjacent vertices) and an independent set (i.e. a set of mutually non adjacent vertices), with possibly edges in between. We determine sharp upper bounds for -backbone coloring numbers of split graphs with tree backbones.