DIMACS/DIMATIA/Rényi Working Group on Graph Colorings and their Generalizations Main Page
DIMACS/DIMATIA/Renyi Tripartite Partnership
Title: On locally constrained graph homomorphisms
We show that the simultaneous existence of a locally surjective and of a locally injective graph homomorphisms between a connected graph G and a connected and finite graph H assures that all such homomorphisms are in fact locally bijective.
We give a short proof of this assertion which unifies previously known partial results of this form. We utilize the notion of universal cover, and relate its properties to the notion of degree refinement, which was used as a principal tool in other works.
Title: L(2,1)-Colored Trees of Maxdegree 3 and Span 5
The L(2,1)-span of G is the smallest k for which G's vertices can be colored from {0,1,...,k} so that adjacent vertices' colors differ by at least two, and colors of vertices at distance two differ. G is span-critical if every edge-reduced subgraph of G has smaller span than G. We characterize recursively all span-critical trees of maximum degree 3 and span 5. A linear-time algorithm decides whether a maxdegree 3 tree is span-critical with span 5.
Joint work by Peter Fishburn and Fred Roberts.
Title: Minimum Covering by Cliques of Perfect Filament Graphs
Let I be a family of intervals on a line L. In the plane, above L, construct to each interval i in I a curve fi connecting its two endpoints, such that if two intervals are disjoint, their curves do not intersect; FI={ fi | i in I} is a family of interval filaments and its intersection graph is an interval filament graph. The interval filament graphs contain the polygon-circle graphs, the circle graphs, the chordal graphs and the cocomparability graphs. Similar families of intersection graphs of filaments can be defined using families of circular-arcs of a circle and families of subtrees of a tree or of a cactus.
In the present talk we describe a polynomial time algorithm to find minimum coverings by cliques for perfect interval filament graphs and similar families.
Title: Real Number Channel Assignments with Distance Conditions
Generalized graph coloring problems arise in connection with efficient channel assignments for networks of radio transmitters, when conditions are imposed due to different levels of interference, based on a problem proposed by F. Roberts. The network is represented by a simple graph, possibly an infinite one. Each vertex must be labelled by a nonnegative integer, and avoiding interference leads to minimum separation requirements for channels at nearby vertices. The task is to minimize the "span", or largest integer, called the lambda number.
Since the initial work on these "lambda labellings" by Griggs and Yeh in the 1980's, there has been steady progress by several groups worldwide, which has been inspired, in part, by the emergence of cellular communications with its regular networks of transmitters.
Motivated by applications and by scaling considerations, we propose a more general model in which the labels and separations are real numbers. This approach leads to new insights about optimal labellings. We have worked out the lambda numbers for paths and cycles with conditions at distances one and two, and we have values or bounds for other interesting graph classes.
Title: Kernel-Solvable Graphs, Core-Solvable Cooperative Games, and List Coloring Conjecture
List Coloring Conjecture claims that the choosability number of a line graph is equal to its chromatic number. In 1995 Galvin proved this conjecture for the line graphs of bipartite graphs (LGBG). His proof is based on the concept of kernel-solvability. The conjecture is derived from a result by Bondy, Boppana ans Siegel on kernel-perfect orientations of the line graphs and from the famous Gale-Shapley (1962) Stable Marriage Theorem. The latter can also be restated in terms of kernels as follows: LGBG are kernel-solvable. This reformulation is due to Maffray (1992).
It is well-known that LGBG are perfect. In 1983 Berge and Duchet conjectured that perfect graphs are kernel-solvable. This conjecture was proved by Boros and Gurvich in 1996 by methods of cooperative game theory. Then a simpler proof, based on a notion of the fractional kernel, was given by Holzman and Aharoni in 1998. Since LGBG are perfect, this result is a generalization of the Gale-Shapley Theorem. Can it be used to generalize Galvin's Theorem and prove the List Coloring Conjecture ?
Interestingly, kernel-solvability is reformulated in terms of game theory in two different ways: as existence of a stable matching for all possible preferences, in case of LGBG, and as core-solvability (stability) of an effectivity function asssigned to a graph, in general. Thus, core-solvability of cooperative games is related to kernel-solvability of graphs and the latter, in its turn, is related to list coloring. So can cooperative games help with List Coloring Conjecture ?
Joint work with Endre Boros.
An adjacent vertex distinguishing edge-coloring of a simple graph $G$ is a proper edge-coloring of $G$ such that no pair of adjacent vertices meets the same set of colors. The minimum number of colors $\chi'_a(G)$ reqired to give $G$ an adjacent vertex distinguishing coloring is studied for graphs with no isolated edge. We proved $\chi'_a(G) \leq 5$ for such graphs with maximum degree $\Delta(G)=3$ and $\chi'_a(G) \leq \Delta(G)+2$ for bipartite graphs. These bound are tight. For $k$-chromatic graphs without isolated edges we prove a weaker result of the form $\chi'_a(G)=\Delta(G)+O({\rm log} k)$.
Title: Coloring powers of chordal graphs and L(2,1)-labeling
A graph G is chordal if it contains no induced cycle of length four or more. We show that the k-th power of a chordal graph G with maximum degree D is O(D^{(k+1)/2})-degenerated. In particular, its second power is O(D^{3/2})-degenerated. The shown bound is best possible for odd values of k and is asymptotically optimal otherwise. From this result, bounds for L(2,1)-labeling of chordal graphs are derived.
Title: Partial Covers and Distance Constrained Labellings of Graphs
An L(2,1)-labelling of a graph is a labelling of the vertices by nonnegative integers such that the labels of adjacent vertices differ by at least 2 and labels of vertices with common neighbors are different. This notion, stemming from the area of frequency assignment and radio networking, generalizes classical graph coloring. We present a structural view to show that distance constrained labellings can be understood as locally injective homomorphisms into the complements of paths. This view naturally suggests to study a more general setting of locally constrained graph homomorphism. Some complexity results about the existence of locally constrained homomorphisms into fixed (parameter) graphs will be surveyed and some presented. The talk is based on joint work with Jiri Fiala.
Title: Irreducible No-hole Colorability of some Classes of Graphs
The channel assignment problem is the problem of assigning radio frequencies to transmitters while avoiding interferences.This problem can be modeled and examined using graph colorings. The concept of L(2,1)-colorings were first studied by Griggs and Yeh as a model of a variation of the channel assignment problem proposed by Roberts. A no- hole coloring is a L(2,1)-coloring which uses all the colors {0,1,2,....k} for some k , introduced by Fishburn and Roberts. An L(2,1)-coloring is irreducible as defined by Fishburn, Roberts, Laskar and Villalpando, if no colors of vertices in the graph can be decreased and yield another L(2,1)-coloring. In this paper we investigate irreducible no-hole colorability of some classes of graphs.In particular, we study bipartite graphs, grid graphs and hyper cube from this point of view.
Joint work with John Villalpando, Gonzaga University.
Title: Between 2- and 3-colorability
The recognition of 3-colorable graphs is known to be an NP-complete problem, while 2-colorable (i.e. bipartite) graphs can be recognized in polynomial time. To make the complexity gap more precise, we study intermediate graph classes between these two extremes and propose a conjecture characterizing the boundary that separates "simple" and "hard" classes. The conjecture is verified by a number of examples.
Title: Using Hypergraph Homomorphisms to Guess Three Secrets
The problem of guessing $k$ secrets (as introduced by Chung, Graham and Leighton, SODA 2001) is a game between two players, an adversary and a seeker. The adversary holds a set of $k$ distinct $n$-bit The seeker wishes to find out as much as possible about these strings, and repeatedly asks the adversary yes-or-no questions about strings. For each question, the adversary chooses one of the $k$ secrets, and correctly answers the question for that string. Because the adversary has so much flexibility, it is impossible for the seeker to learn any one of the secrets with absolute certainty.
The maximum that can be be learned is an intersecting family of k sets that contains the secret set of strings. This can be attained with a relatively simple strategy that uses space 2^O(n), where n is the bit-size of the secrets. The major open problem in the area is developing efficient strategies to find the intersecting family. Previously, polynomial time methods were known only for k=2 (Alon, Guruswami, Kaufman, Sudan SODA 2002; Chung, Graham, Lu SODA 2002)
We present the first polynomial-time strategy for solving the problem of guessing _three_ secrets. We give both adaptive and oblivious strategies that run in polynomial time. The adaptive strategy makes $O(n)$ many queries and the oblivious strategy makes $O(n^5)$ many queries. The search procedure is based on the partial order induced by homomorphisms between three-uniform intersecting hypergraphs and combinatorial properties of three-uniform, intersecting hypergraph cores.
This is joint work with Daniele Micciancio.
Title: Local chromatic number and Sperner capacity
The local chromatic number of a graph $G$ was introduced in a 1986 paper by ErdHos, Furedi, Hajnal, Komjath, Rodl, and Seress, as the minimum number of colors that some vertex is guaranteed to see in its closed neighbourhood if the vertices of the graph are properly colored. It is shown in the above mentioned paper that this invariant can be arbitrarily much less than the chromatic number of $G$. We show that, nevertheless, the local chromatic number is bounded from below by the fractional chromatic number. This implies also a relation between the local chromatic number and the Shannon capacity of a graph. We generalize this to the directed case by introducing a directed version of the local chromatic number and showing that it provides an upper bound for Sperner capacity. We use this inequality to give tight bounds on the Sperner capacity of all but one of the oriented versions of odd cycles.
The results are joint with Janos Korner and Concetta Pilotto.
Title: L(2,1)-Labelings of Products of Two Cycles
An L(2,1)-labeling of a graph is an assignment of nonnegative integers to its vertices so that adjacent vertices get labels at least two apart and vertices at distance two get distinct labels. The Lambda-number of a graph G, denoted by Lambda(G), is the minimum range of labels taken over all of its L(2,1)-labelings. We show that the Lambda-number of the product of any two cycles is 6, 7 or 8. In addition, we provide complete characterizations for the products of two cycles with Lambda-number exactly equal to each one of these values.
(This is a joint work with Christopher Schwarz.)
Title: Choosability problems for $(d,s)$-colorings
Joint work with A. Kohl, J. Schreyer, and M. Voigt.
A $(d,s)$-coloring of a graph is an assignment $f$ of integers to the vertices in such a way that $|f(u)-f(v)|\geq d$ for every edge $uv$, and $|f(u)-f(v)|\geq s$ if $u$ and $v$ are at distance two apart.
We consider the list coloring version of the problem, i.e.\ where a list $L_v$ of integers (colors) is given for each vertex $v$, and $f(v)\in L_v$ must hold for every $v$. The graph invariant $\chi^{d,s}_{\ell}$, analogous to the known concept of choice number (list chromatic number) is the smallest $k$ such that the graph in question admits a list $(d,s)$-coloring whenever $|L_v|\geq k$ for all $v$.
We present estimates and tight results on $\chi^{d,s}_{\ell}$ for some particular types of graphs.
Title: Irreducibility of L(2,1)-Colorings and the Inh-Colorability of unicylic and hex graphs
An L(2,1)-coloring of a graph is a labelling of the vertices by nonnegative integers such that adjacent vertices differ in label by at least 2 and the labels of vertices at distance two differ by at least 1. The span of an L(2,1)-coloring is the largest label used by the coloring. A no-hole coloring of a graph is an L(2,1)-coloring where every color class less than the span is non-empty. An irreducible L(2,1)-coloring is an L(2,1)-coloring such that decreasing the label of any vertex violates an L(2,1)-constraint. An inh-coloring of a graph is an L(2,1)-coloring that is both no-hole and irreducible. Since not all graphs can be colored with inh-coloring, a graph which can be colored with an inh-coloring is called inh-colorable.
In this talk we examine the irreducible property and its relationship to the span. We discuss unicylic and hex graphs and show that these classes of graphs are inh-colorable. For both of these classes of graphs, we will provide an upper bound for the span of an inh-coloring.
Joint work with Renu Laskar, Clemson University.
Title: Real Number Graph Labeling for the Triangular Lattice and the Square Lattice
Fred Roberts (1991) surveyed the graph $T$-coloring problem, which comes from the radio channel assignment problem. Griggs and Yeh (1992) introduced the integer graph $L(k_1,k_2)$ labeling problem, related to the graph $T$-coloring problem. We extend it to the real number graph labeling problem, in which we allow the labels to be nonnegative real numbers, instead of only nonnegative integers. An $L(k_1,k_2,\cdots,k_p)$-labeling of graph $G$ is an assignment of nonnegative real numbers to the vertices of $G$ with $x\in V(G)$ labeled $f(x)$, such that $|f(u)-f(v)|\ge k_i$ if $u$ and $v$ are at distance $i$ apart, where $k_i\in [0,\infty)$. We denote by $\lambda(G;k_1,k_2,\cdots,k_p)$ the infimum span over such labelings $f\in L(k_1,k_2,\cdots,k_p)(G)$.
For $p=2$, we have $\lambda(G;k_1,k_2)=k_2\lambda(G;k,1)$ for real numbers $k_1\ge 0, k_2>0$ and $k={k_1\over k_2}$. Here we have determined most of the values $\lambda(G;k,1)$, for $G$ being the triangular lattice or the square lattice. We introduce some properties of labelings of the triangular lattice, the square lattice, such as strip property, regular tiling, arithmetic progression. Those properties are helpful for us to find optimal labelings in straightforward way, and hence the $\lambda$ number (the minmum span).
Previous: Program
Workshop Index
DIMACS Homepage