The workshop is the second meeting of DIMACS/DIMATIA/Renyi Working Group on Graph Colorings and their Generalizations, whose first meeting took place at DIMACS Center, Rutgers University, Piscataway, New Jersey at October 13 - 15, 2003.

The central topic of the workshop is generalization of graph colorings, motivated by practical applications like channel assignment in communications, traffic phasing, fleet maintenance, task assignment, and others. On the workshop will be surveyed and investigated such generalizations of graph coloring as T-colorings, list colorings, L(2,1)-colorings, and set colorings, with an emphasis on the graph coloring concepts that arise from channel assignment problems, and design of graph coloring algorithms for new models and applications.

Back row: Zdenek Dvorak, Dan Kral, Joe Gimbel, William Cuckler, David Wood, Jiri Fiala

Front row: Nicholas Weininger, Brenda Latka, Vladimir Gurvich, Jan Kratochvil, Jarik Nesetril, Robert Babilon.

Yared Nigussie and Riste Skrekovski are not present at the picture

**Robert Babilon, Vit Jelinek,**__Dan Kral__, Pavel Valtr:*Graphs of graphs*Let G be a graph with two types edges forming sets E1 and E2. We define chi_G(x), 0<=x<=1, to be the smallest (real) number K such that the vertices of $G$ can be labaled by (real) numbers between 1 and K (inclusively) and any two vertices joined by an edge of the first kind receive numbers whose difference is at least 1 and any two vertices joined by an edge of the second kind receive numbers whose difference is at least x. It is easy to see that chi_G(0) is the chromatic number of the graph with the edge set E1 and chi_G(1) is the chromatic number of the graph with the union of both edge sets E1 and E2.

The definition of chi_G(x) is motivated by the notion of L(p,q)-labeling which is studied intensively in connection with the efficient radio frequency assignments. Consider a graph H. Let G be the graph with the same vertex set as G, E1 the edge set of H and E2 the edge set of the second power of H. It can be shown that lambda_p,q(G)=p(chi_G(q/p)-1).

We study combinatorial properties of functions chi_G(x). It is easy to show that for each graph G, chi_G(x) is a piecewise linear function consisting of at most n^2 segments where $n$ is the order of G. We provide a better (and tight) bound for the case when chi_G(x) is assumed to be convex. Our main result is the following (surprising) fact: Let Gamma be the set of all functions chi_G(x) for finite graphs G. For any integers k1<=k2, the number of functions f from Gamma with f(0)=k1 and f(1)=k2 is finite. Let us remark that this result can also be extended to infinite graphs with finite chromatic numbers.

__Jiri Fiala__, Jan Kratochvil:*NP-hardness of the L(2,1)-labeling problem on regular graphs*The L(2,1)-labeling is an assignment of integral labels to vertices of a graph such that labels of adjacent vertices differ by at least two, while vertices at distance two have distinct labels.

We show that for all k greater than two the decision problem whether a k-regular graph admits an L(2,1)-labeling of span k+2 is NP-complete.__Vladimir Gurvich__:*Complete Edge-n-Colored Graphs, Applications and Problems*A complete edge-n-colored graph G=(V; E1,...,En) is a complete graph whose edges are colored by n colors c: E->{1,...,n}, i.e. the edge-set E is partitioned by subsets E1,...,En. These graphs are related to positional games with perfect information and to box-partitions.

The following problem is open since 1971. Let G contains a 3-colored triangle, say v1,v2,v3 from V such that c(v1,v2)=3, c(v2,v3)=1, c(v3,v1)=2. Prove that for each i=1,...,n there is a vertex-subset C_i of V such that

- for every v,v' from Ci the edge (v,v') is NOT of color i;
- Ci is a MAXIMAL set satisfying (1.) that is an edge of color i appears in every superset of Ci;
- the common intersection of all Ci, i=1,...,n is empty,

The general claim follows from the case n=3.

**Jiri Fiala,**__Jan Kratochvil__, Attila Por:*Complexity of partial covers of Theta graphs*Partial results on the computational complexity of partial covers of graphs with two vertices of degree higher than two. Namely an NP-hardness reduction based on a new result from number theory.

Partial covers of graphs correspond to H(2,1)-labelings, a structural generalization of L(2,1)-labelings motivated by the freqency assignment problem.**Jaroslav Nesetril,**__Yared Nigussie__:*The interval (Cg,Cg+eps)*For every eps>0 and every odd integer g>3, let Cg+eps denote any K4-minor-free graph such that the cycle Cg is homomorphic to Cg+eps and Cg+eps is not homomorphic to Cg. We prove there exists an infinite sequence of real numbers eps>eps1>eps2>... such that for all i epsi>1 and the subinterval (Cg+eps(i-1), Cg+eps(i+1)) (ordered by homomorphism) contains a class of K4-minor-free graphs that induces a universal partial order. This shows a surprising richness of arbitrarily small intervals within the class of series parallel graphs.

__Jaroslav Nesetril__:*Duality of Graph Homomorphisms*__Riste Skrekovski__:*Some coloring problems of planar graphs*In the talk will be presented several coloring problems about planar graphs.

__Nicholas Weininger__:*Correlation Properties of Random Homomorphisms*Given a bipartite graph G and an integer q >= 2, pick a proper q-coloring of G uniformly at random. An old, apparently folkloric result says that the resultant distribution exhibits pairwise positive correlation, in the sense that if x,y are two vertices in the same color class of G, knowing x is red makes y more likely to be red. We may naturally ask whether this correlation property also holds for random homomorphisms from G to some more general class of target graphs H. It turns out that there are pairs (G,H) for which it does not hold, leaving the question: what are the necessary restrictions on G and/or H to make it hold? We will discuss some possible answers to this question and state a few recent partial results.

Participation is by invitation only. To inquire please contact Jan Kratochvil, Jaroslav Nesetril or Jiri Fiala.

There is no fee charged for invited attendees.

June 2004 Jan Kratochvil