An Application of Stahl's Conjecture About the k-Tuple Chromatic Numbers of Kneser Graphs

Graph coloring is an old subject with many important applications. Variants of graph coloring are not only important in their various applications, but they have given rise to some very interesting mathematical challenges and open questions. Our purpose in this mostly expository paper is to draw attention to a conjecture of Saul Stahl's about one variant of graph coloring,

k

-tuple coloring. Stahl's Conjecture remains one of the long-standing, though not very widely known, conjectures in graph theory. We also apply a special case of the conjecture to answer two questions about

k

-tuple coloring due to N.V.R. Mahadev.

An interesting and important variant of ordinary graph coloring involves assigning a set of

k

colors to each vertex of a graph so that the sets of colors assigned to adjacent vertices are disjoint. Such an assignment is called a

k-tuple coloring

of the graph.

k

-tuple colorings were introduced by Gilbert (1972) in connection with the mobile radio frequency assignment problem (see Opsut & Roberts, 1981; Roberts, 1978, 1979; Roberts & Tesman, 2005). Other applications of multicolorings include fleet maintenance, task assignment, and traffic phasing. These are discussed in Opsut and Roberts (1981); Roberts (1979); Roberts and Tesman (2005) and elsewhere. Among the early publications on this topic are Chvátal, Garey, and Johnson (1978); Clarke and Jamison (1976); Garey and Johnson (1976); Scott (1975); Stahl (1976). Given a graph

G

and positive integer

k

, we seek the smallest number

t

so that there is a

k

-tuple coloring of

G

using colors from the set {1,2,...,

t

}. This

t

is called the

k-th multichromatic number

or

k-tuple chromatic number

of

G

and is denoted by

?

k

(

G

). Of course, if

k

= 1,

?

k

(

G

) is just the ordinary chromatic number

?

(

G

)