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

Svata Poljak and Fred S. Roberts ()
Additional contact information
Fred S. Roberts: Rutgers University

A chapter in The Mathematics of Preference, Choice and Order, 2009, pp 345-352 from Springer

Abstract: 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)

Keywords: Planar Graph; Chromatic Number; Task Assignment; Discrete Mathematic; Graph Coloring (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:stcchp:978-3-540-79128-7_20

Ordering information: This item can be ordered from
http://www.springer.com/9783540791287

DOI: 10.1007/978-3-540-79128-7_20

Access Statistics for this chapter

More chapters in Studies in Choice and Welfare from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().