-BACKBONE COLORING NUMBERS OF SPLIT GRAPHS WITH TREE BACKBONES

A.N.M. Salman

Abstract


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 an
economical 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.

Full Text:

PDF

Refbacks

  • There are currently no refbacks.