- First Meeting
- Dates: October 13 - 15, 2003
Location: DIMACS Center, Rutgers University, Piscataway, New Jersey- Second Meeting
- Dates: August 2 - 4, 2004
Location: Prague, Czech Republic- Third Meeting
- Date: April 21 - 22, 2005
Location: The Rényi Institute, Budapest, Hungary
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, chT(G), the smallest k so that a graph G always has a T-coloring when sets of k allowable colors are given at each vertex. Very little is known about list T-colorings or T-choice numbers beyond this initial work, and we shall explore these concepts. Results about ordinary choice numbers (which arise when T = {0}), cited in [1, 4, 7, 20, 24] and elsewhere, should prove helpful here.
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 rx to each vertex x of a graph. These set colorings are considered in [13, 25, 26, 27, 29, 30] and arise from problems of telecomunications and task assignment. It seems natural to develop a theory of list set colorings for these types of assignments and we shall explore this idea.
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.445n) 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.3446n) time. Lawler observed that 4-colorability can
be done in 2npoly(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 Kn.
[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.3446n): 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.415n) 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