DIMACS Center, Rutgers University, Piscataway, New Jersey

**Organizers:****Fred S. Roberts**, DIMACS, froberts@dimacs.rutgers.edu**Stephen Hartke**, Rutgers University, hartke@math.rutgers.edu

DIMACS/DIMATIA/Rényi Working Group on Graph Colorings and their Generalizations Main Page

DIMACS/DIMATIA/Renyi Tripartite Partnership

In ordinary graph coloring, we assign a color f(*x*) to each
vertex *x* of a graph *G* so that two vertices that are neighbors
get different colors.
In many applications, there is an extra complication. There are some
acceptable colors for each vertex and the color assigned to a vertex
must be chosen from the set of acceptable colors. For instance, in
channel assignment ([31]), we specify a set of acceptable
channels for each transmitter (vertex) and in traffic phasing
([31]) a set of acceptable times to schedule a traffic
stream (vertex). To formalize this idea, we let *S*(*x*) denote a
nonempty set of integers assigned to vertex *x* of graph *G* and call
*S* a *list assignment* for G. We seek a graph coloring *f* so
that for every *x* *V*, we have *f*(*x*) *S*(*x*). Such a coloring is
called a * list coloring* for (*G*,*S*) (see
[1, 7, 20]). Among the problems we
shall explore will be
to formalize measures of how many changes are needed in a list
assignment in order for a list coloring to exist. Recent work of
Woodall [38] and others on variants of the notion of ``defective
coloring'' are relevant to this problem.

If *G* is a graph and *T* is a set of
nonnegative integers, a *T*-*coloring* assigns a nonnegative
integer *f*(*x*) to each vertex *x* of *G* so that neighboring vertices
get colors
whose separation is not in the set *T*. The notion of *T*-coloring
was introduced by Hale [15] in connection with the problem of
assigning frequencies to radio and television transmitters. Here, the
vertices represent transmitters, an edge means interference, *f*(*x*) is
the frequency assigned to *x*, and the set *T* represents
disallowed separations between channels assigned to interfering
transmitters. There has been a considerable literature
devoted to the study of different notions of optimality for
*T*-colorings, especially the notion of span; see
[3, 22, 32, 37] for
surveys. A widely-studied question is this: Under what circumstances
does a greedy algorithm on *G* give an optimal *T*-coloring? This is
not yet totally settled.
The idea of list coloring
also enters here. When a set or list of possible
colors is
specified for each vertex, we sometimes seek a *T*-coloring, called a
* list T-coloring*, in which the color assigned to a vertex is
chosen from its list. Tesman [37] introduced list *T*-colorings
and in particular the *T*-choice number, *ch _{T}*(

Our work on generalizations of graph colorings will be partially
motivated by a project at NATO, where the optimization problems
arising in *T*-coloring are impossible to solve exactly because of
their size. This led Tim Lanfear at NATO to suggest a heuristic
algorithm for so-called 2-level *T*-coloring problems. The algorithm
was based on the idea that a channel assignment that doesn't allow
``holes'' or omitted channels is likely to be an efficient one.
Lanfear's idea suggested that we should study channel assignments with
``no holes.'' Papers [8, 11, 12] are recent papers
on this subject, building on older ones
[33, 34]. We will study ``no-hole'' colorings under
various generalized models of graph coloring.

Lanfear's work gave rise to a model of 2-level channel assignment
defined precisely by Griggs and Yeh [14, 39]. This is an
*L*(2,1)-*coloring* of a graph. Here, we assign nonnegative
integer channels to the vertices of a graph so that if two vertices
are joined by an edge in the graph, their channels differ by at least
two and if the two vertices have a common neighbor, then their
channels differ. We will build on an extensive literature about such
colorings to investigate such questions as when a greedy procedure
gives rise to an optimal *L*(2,1)-coloring. Optimal *L*(2,1)-coloring for
a general graph was shown NP-complete in [10] for every fixed
number of available colors. This problem is known to be solvable in
polynomial time for trees, even when the number of colors is part of
the input. On the other hand, complexity of *L*(*p,q*)-colorings of
trees is still open. In an *L*(*p,q*)-*coloring* we require that
channels assigned to adjacent vertices differ by at least *p* and
channels assigned to vertices with a common neighbor differ by at
least *q*. The feeling that q >1 identifies a more difficult problem
is justified in [9], where it is shown that the problem becomes
NP-complete if some vertices of the input tree are preassigned
channels, or are * precolored*, whereas for *q*=1 the precolored
version remains polynomially solvable on trees. We will investigate
the complexity of *L*(*p,q*)-coloring under various special assumptions
about the graphs and the precoloring.

Other generalized graph coloring problems of interest involve *
set colorings* where we assign a set *C*(*x*) to each vertex of a graph
so that if *x* and *y* are adjacent, *C*(*x*) and *C*(*y*) are
disjoint. The *n*-tuple colorings are
a special case where each *C*(*x*) is an *n*-element set.
We shall investigate the
*k-tuple T-colorings* studied by Tesman [37]. Here
each set *C*(*x*) has *k* elements and an edge between *x* and *y*
implies that the distance between an element of *C*(*x*) and an element
of *C*(*y*) is never in the set *T*. Little work has been done on this
notion since Tesman's initial investigation. We shall also be
interested in set colorings
involving assignment of a set of integers of size at least *r _{x}*
to each vertex

The ideas described here have analogues for edge colorings and we shall investigate them as well. Some examples of relevant work can be found in [17, 18, 19].

The group will also investigate algorithms for graph
coloring. Assuming NP-complete problems are indeed hard, it is still
of interest to find exact algorithms for them that are as fast as
possible. As noted by Beigel and Eppstein [2], there are not
many papers on exact algorithms for NP-complete problems; they give a
short bibliography of such papers. The problem of finding exact
algorithms for graph coloring, which is perhaps the most fundamental
of all NP-hard graph problems, is especially intriguing. The obvious
back-tracking algorithm for coloring an *n* vertex graph has
complexity *n*^{(n)} time. Twenty years ago, Lawler [21]
gave an algorithm that runs in *O*(2.445^{n}) time. This is still the
best known result. Graph 3-coloring has been considered by a few
authors, Lawler [21], Schiermeyer [35] and Beigel and
Eppstein [2], who have the best existing exact algorithm, which
runs in *O*(1.3446^{n}) time. Lawler observed that 4-colorability can
be done in 2^{n}*poly*(*n*). All of these approaches are based on dynamic
programming and backtrack search. Recent work by Paturi, Pudlák, Zane
and Saks [28] and by Schöning [36] suggest other
approaches. In [28], a simple randomized algorithm is
developed for *k*-satisfiability using a randomized greedy algorithm
combined with resolution. In [36], a simple random walk
approach is used to find an algorithm for the constraint satisfaction
problem, a common generalization of the *k*-satisfiability and
*k*-coloring problems. We shall investigate ways to apply some of the
techniques used for *k* satisfiability to *k*-coloring. There are
various possibilities for improving existing algorithms, using a more
detailed analysis to prune the backtrack search, and we shall
investigate these as well. We shall also ask whether these ideas for
ordinary graph coloring give us insight into algorithms for
*T*-colorings, *L*(2,1)-colorings, and *n*-tuple colorings. (For
earlier related work, see for example [5, 6].)

Another algorithmic question is finding good approximation algorithms for graph coloring and its variants. Complexity theory results tell us that it is highly unlikely that any polynomial-time heuristic can guarantee a number of colors that is within any constant factor of optimal ([23]). However, for graphs that arise in practical applications, we may be more fortunate. In 1993, DIMACS conducted an ``Algorithm Implementation Challenge'' on graph coloring and other problems (see [16]). This yielded the conclusion that a variety of heuristic search techniques could succeed in constructing reasonably good colorings. One topic for this working group will be to consider how such approaches can best be extended to generalized graph coloring and channel assignment applications.

This working group will interact closely with the working group on
Algebraic and Geometric Methods in Combinatorics, which will study
homomorphisms of graphs into a target graph *H*, so-called
*H*-colorings. An ordinary graph coloring is an *H*-coloring where the
target graph *H* is the complete graph *K _{n}*.

[1] Alon, N., ``Restricted Colorings of Graphs,'' in
K. Walker (ed.), * Surveys in Combinatorics*, Proc. 14th British
Combinatorial Conference, London Math. Society Lecture Note Series
187, Cambridge University Press, Cambridge, UK, 1993, 1-33.

[2] Beigel, R., and Eppstein, R., ``3-Coloring in Time
*O*(1.3446^{n}): A No-MIS Algorithm,'' * Proc. 36th IEEE Symposium
on Foundations of Computer Science*, 1995, 444-452.

[3] Bonias, I., ``*T*-Colorings of Complete Graphs,''
Ph.D. Thesis, Department of Mathematics, Northeastern University,
Boston, MA, 1991.

[4] Brown, J.I., Kelly, D., Schönheim, J., and Woodrow,
R.E., ``Graph Coloring Satisfying Restraints,'' * Discrete
Math.*, ** 80**, (1990), 123-143.

[5] Castelino, D., Hurley, S., and Stephens, N., ``A Tabu Search
Algorithm for Frequency Assignment, ``* Annals of Operations Research*, **
63**, (1996), 301-319.

[6] Dorne, R., and Hao, J.K., ``Tabu Search for Graph
Coloring, *T*-coloring and Set *T*-coloring,'' in I.H. Osman, et
al. (eds.), * Metaheuristics 98:
Theory and Applications*, Kluwer Academic Publishers, 1998.

[7] Erdós, P., Rubin, A.L., and Taylor, H.,
``Choosability in Graphs,'' * Congr. Numer.*, ** 26**, (1979),
125-157.

[8] Fiala, J., and Kratochvíl, J., ``Partial Covers of Graphs,'' KAM-DIMATIA Technical Report 2000-479, 2000 (accepted by ISAAC 2001, Christchurch, December 2001).

[9] Fiala, J., Kratochvíl, J., and Proskurowski, A, ``Distance Constrained Labeling of Precolored Trees,'' accepted to ICTCS 2001, Torino, October 2001

[10] Fiala, J., Kloks, T., and Kratochvíl, J.,
``Fixed-parameter Complexity of $\lambda$-colorings,'' in
P. Widmayer, G. Neyer, S. Eidenbenz (eds.), * Graph Theoretic Concepts in
Computer Science, Proceedings WG '99, Ascona, June 1999*, Lecture
Notes in Computer Science 1665, Springer Verlag, 1999, 350-363.

[11] Fishburn, P.C., and Roberts, F.S., ``Full Color Theorems
for *L*(2,1)-Colorings,'' DIMACS Technical Report 2000-08, DIMACS
Center, Rutgers University, Piscataway, NJ, 2000.

[12] Fishburn, P.C., and Roberts, F.S., ``No-Hole
*L*(2,1)-Colorings,'' DIMACS Technical Report 2001-10, DIMACS
Center, Rutgers University, Piscataway, NJ, 2001.

[13] Gilbert, E.N., Unpublished Technical Memorandum, Bell Telephone Laboratories, Murray Hill, NJ, 1972.

[14] Griggs, J.R., Yeh, R.K., ``Labelling Graphs with a
Condition at Distance 2,'' * SIAM J. Discrete Math.*, ** 5**,
(1992) 586-595.

[15] Hale, W.K., ``Frequency Assignment: Theory and
Applications,'' *Proc. IEEE*, ** 68**, (1980), 1497-1514.

[16] Johnson, D.S., and Trick, M.A., * Cliques,
Coloring, and Satisfiability:
Second DIMACS Implementation Challenge*, DIMACS Series, Vol. 26,
American Mathematical Society, Providence RI, 1996.

[17] Kahn, J., ``Coloring Nearly-disjoint Hypergraphs with
*n*+*o*(*n*) Colors, *
J. Combin. Theory*, ** A 59**, (1992), 31-39.

[18] Kahn, J., ``Asymptotics of the Chromatic Index for
Multigraphs,'' * J. Combin. Theory*, ** B 68**, 1996, 233-254.

[19] Kahn, J., ``Asymptotics of the List-chromatic Index
for Multigraphs,'' * Random Structures Algorithms*, ** 17**, (2000), 117-156.

[20] Kratochvíl, J., Tuza, Z., and Voigt, M., ``New
Trends in the Theory of Graph Colorings: Choosability and List
Coloring,'' in R.L. Graham, J. Kratochvíl, J. Ne\v{s}et\v{r}il,
and F.S. Roberts (eds.), * Contemporary Trends in Discrete
Mathematics*, DIMACS Series, Vol. 49, American Mathematical Society,
Providence, RI, 1999, 183-197.

[21] Lawler, E., ``A Note on the Complexity of the Chromatic
Number Problem,'' * Information Processing Letters*, ** 5**,
(1976), 66-67.

[22] Liu, D.D., ``Graph Homomorphisms and the Channel Assignment Problem,'' Ph.D. Thesis, Department of Mathematics, University of South Carolina, Columbia, SC, 1991.

[23] Lund, C., and Yannakakis, M., ``On the
Hardness of Approximating Minimization Problems,'' * J.ACM*, **
41**, (1994),
960-981.

[24] Mahadev, N.V.R., and Roberts, F.S., ``Amenable
Colorings,'' * Discrete Applied Math.*, ** 76**, (1997),
225-238.

[25] Opsut, R.J., and Roberts, F.S., ``On the Fleet
Maintenance, Mobile Radio Frequency, Task Assignment, and Traffic
Phasing Problems,'' in G. Chartrand, et al. (eds.), * The Theory
and Applications of Graphs*, Wiley, New York, 1981, 479-492.

[26] Opsut, R.J., and Roberts, F.S., ``*I*-colorings,
*I*-phasings, and *I*-intersection Assignments for Graphs, and their
Applications,'' * Networks*, ** 13**, (1983), 327-345.

[27] Opsut, R.J., and Roberts, F.S., ``Optimal
*I*-intersection Assignments for Graphs: A Linear Programming
Approach,'' * Networks*, ** 13**, (1983), 317-326.

[28] Paturi, R, Pudlák, P, Saks, M.E, and Zane, F.,
``An Improved Exponential-time Algorithm for *k*-satisfiability,''
* Proc. 39th IEEE Symp. on Foundations of Computer Science*, 1998,
628-627.

[29] Raychaudhuri, A.,
``Optimal Multiple Interval Assignments in Frequency Assignment
and Traffic
Phasing,'' * Discrete Applied Mathematics*, ** 40**, (1992),
319-332.

[30] Roberts, F.S., ``On the Mobile Radio Frequency
Assignment Problem and the Traffic Light Phasing Problem,'' *
Annals NY Acad. Sci.*, ** 319**, (1979), 466-483.

[31] Roberts, F.S., ``From Garbage to Rainbows:
Generalizations of Graph Coloring and their Applications,'' in
Y. Alavi, G. Chartrand, O.R. Oellermann, and A.J. Schwenk (eds.), *
Graph Theory, Combinatorics, and Applications*, Vol. 2, Wiley, New
York, 1991, 1031-1052.

[32] Roberts, F.S., ``*T*-Colorings of Graphs: Recent
Results and Open Problems,'' * Discrete Math.*, ** 93**, (1991),
229-245.

[33] Roberts, F.S., ``No-hole 2-distant Colorings,''
* Mathl. Comput. Modelling*, ** 17**, (1993) 139-144.

[34] Sakai, D., and Wang, C., ``No-hole (*r*+1)-distant
Colorings,'' * Discrete Math.*, ** 119**, (1993) 175-189.

[35] Schiermeyer, I., ``Deciding 3-colourability in Less than *O*(1.415^{n})
Steps,'' * 19th Workshop Graph Theoretic Concepts in Computer
Science*, Springer-Verlag, 1994, 177-182.

[36] Schöning, U., ``A Probabilistic Algorithm
for *k*-SAT and Constraint Satisfaction Problems,''
* Proc. 40th IEEE Symp. on Foundations of Computer Science*,
1999, 410-414.

[37] Tesman, B., ``*T*-Colorings, List *T*-Colorings, and
Set *T*-Colorings of Graphs,'' Ph.D. Thesis, Department of
Mathematics, Rutgers University, New Brunswick, NJ., October 1989.

[38] Woodall, D., ``Defective Choosability Results for Outerplanar and Related Graphs,'' preprint, University of Nottingham, Nottingham, England, 2001.

[39] Yeh, R.K., ``Labeling Graphs with a Condition at Distance Two,'' Ph.D. Thesis, University of South Carolina, 1990.

Working Group Index

DIMACS Homepage

Contacting the Center

Document last modified on November 5, 2002.