INSTANCE: A tree T = (V,E), a positive integer K.

QUESTION: Does T have a complete K-coloring?

A coloring of the vertices of a tree T with K colors {1,2,...,K} is called complete if (i) adjacent vertices are assigned different colors, and (ii) for every pair i,j of distinct colors there exists a pair of adjacent vertices colored i and j. The maximum integer K for which a graph G has a complete K-coloring is called the achromatic number of G. For many years it was not known whether the achromatic number of a tree can be found in polynomial time. This problem is known to be NP-complete for arbitrary graphs and solvable in polynomial time for fixed K [Bodlaender, 1989]. [F. Harary and S. Hedetniemi, The achromatic number of a graph, J. Combin. Theory 8 (1970) 154-161] [H.L. Bodlaender, Achromatic number is NP-complete for cographs and interval graphs, Inform. Process. Lett. 31 (1989) 135-138] [UPDATE: this problem has been shown to be NP-complete for trees; I will provide the reference shortly. It now remains to determine for what classes of trees can the achromatic number be determined in polynomial time. There is a fairly large literature on the achromatic number which I cannot provide at this time.]

INSTANCE: A tree T = (V,E), a positive integer K.

QUESTION: Does T have a complete partition of order >= K?

A partition of the vertices of T, {V₁, V₂, ... , V_k} is called complete if for every i,j there exists a vertex in V_i and a vertex in V_j which are adjacent. The maximum order of a complete partition of V is called the pseudo-achromatic number of a graph. Defined many years ago by R. Gupta, very little is known about this parameter of a graph. The NP-completeness of the decision problem for the pseudo-achromatic number has been shown by James Knisely [1992] for arbitrary graphs. The complexity for trees remains an open problem.

INSTANCE: A graph G = (V,E), a positive integer K.

QUESTION: Does G have a Grundy coloring which uses >= K colors?

In a sequential coloring of the vertices of a graph G the vertices are ordered in any fashion v₁, v₂, ... , v_n, and are colored in this order subject to one or more rules. For example, a Grundy coloring is a sequential coloring in which the rule is that the color assigned to each vertex is the smallest available color (where two vertices which are adjacent must receive different colors). The Grundy number of a graph is the largest number of colors that can be used in any Grundy coloring of G. There exists an O(n) algorithm for determining the Grundy number of an arbitrary tree [Beyer, Hedetniemi and Mitchell]. There is also a trivial algorithm for determining the Grundy number of a cograph [as pointed out by Derek Corneil]. Can you construct a polynomial algorithm for determining the Grundy number for any other family of graphs? Corneil suggests that you try to construct a Grundy algorithm for two-trees. I might suggest that you try to compute the Grundy number of an interval graph. The NP-completeness of this problem has been determined for directed graphs [cf. Garey and Johnson's NP-completeness book]. [C.A. Christen and S.M. Selkow, Some perfect coloring properties of graphs, J. Combin. Theory B 27 (1979), 49-59] [T. Beyer, S.M. Hedetniemi and S.T. Hedetniemi, A linear algorithm for the Grundy number of a tree, Proc. Thirteenth Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, 1982, 351-363] The NP-completeness of this problem, even for bipartite and chordal graphs has been settled by Alice McRae [January 1994].

INSTANCE: A tree T = (V,E), a positive integer K.

QUESTION: Does T have a partial Grundy coloring which uses >= K colors?

A partial-Grundy coloring is a sequential coloring in which the rule is that the color assigned to each vertex can be any color that has already been used or the next highest unused color if no previously used color produces a legitimate coloring. The partial Grundy number of a graph G is the largest number of colors that can be used in any partial-Grundy coloring of G. Can you construct an algorithm for computing the partial-Grundy number of an arbitrary tree? [UPDATE: The NP-completeness of this problem has been settled, even for bipartite graphs and chordal graphs, by Alice McRae (February, 1994)], but no tree algorithm is known.

INSTANCE: A tree T = (V,E).

QUESTION: Is T graceful?

A tree T with n vertices is graceful if there is a 1-1 function f: V --> {1,2,...,n} such that the set {|f(u)-f(v)| : uv in E} = {1,2,...,n-1}.

INSTANCE: A tree T = (V,E).

QUESTION: Is T 1-sequential?

A graph G is 1-sequential if there exists an assignment function h: V --> N = {1,2,...} such that h(V) union {|h(u)-h(v)| for all uv in E} = {1,2, ... , |V|+|E|}.

Peter Slater points out that "1-sequential" and "simply sequential" mean the same thing in the following papers: [1] P. J. Slater, On problems concerning sequential and simply sequential graphs, unpublished. [2] D.W. Bange, A.E. Barkauskas and P.J. Slater, Simply sequential and graceful graphs, Proc. Tenth Southeastern Conf. on Combinatorics, Graph Theory and Computing, (1979), 155-162. 155-162, 1979, bange, barkauskas and pjs.

[1] was never published - essentially everything in it appears in [2], including Slater's conjecture from [1] that all trees are simply sequential. Slater's conjecture is considerably weaker than Ringel's, and hence might be more easily proven. A theorem in [2] states: Theorem. A tree T is graceful if and only if T is simply sequential via a function f such that f is odd for each vertex.

INSTANCE: A graph G = (V,E).

QUESTION: Is G antimagic? i.e. does there exist a one-to-one function f: E --> {1,2, ... , |E|} such that the induced weight at each vertex is distinct, where the induced weight at a given vertex v equals the sum of the values of all edges incident to v?

It is conjectured that all connected graphs are antimagic. [NOTE: I have a recollection that this problem has been solved; I need to ask around for this one.]

INSTANCE: A tree T = (V,E), a positive integer K.

QUESTION: Does T have an irregularity sum <= K?

A problem similar to ANTIMAGIC GRAPH is obtained if we are allowed to assign any positive value to the edges of E, such that the induced weight at each vertex is distinct. This is called an irregular assignment and G is called vertex distinguishable if it has an irregular assignment. The irregularity sum of a graph G is the minimum sum of the induced weights of all vertice s, in an irregular assignment for G. IRREFULARITY TREE SUM is an open proble.m

INSTANCE: A tree T = (V,E), a positive integer K.

QUESTION: Does T have a harmonious K-coloring, i.e. a function f:V --> {1,2,...,K} such that for every edge (u,v) in E, the pair (f(u),f(v)) is unique?

INSTANCE: A graph G = (V,E).

QUESTION: Does T have a total coloring with <= max deg + 2 colors?

A total coloring of a graph G = (V,E) is an assignment of colors to the vertices and the edges of G such that every pair of adjacent vertices, every pair of adjacent edges and every vertex and incident edge pair receive different colors. The total chromatic number of a graph G equals the minimum number of colors needed in a total coloring of G. It is an old conjecture of Behzad that for every graph G, the total chromatic number equals the maximum degree of a vertex in G plus one or the maximum degree plus two. [M. Behzad, Graphs and their chromatic numbers, Ph.D. Thesis, Michigan State University, 1965] [A.G. Chetwynd, Total colourings of graphs - a progress report, Graph Theory, Combinatorics, and Applications, Vol. 1, Alavi, Chart rand, Oellermann and Schwenk, Eds., Wiley Interscience, 1991]

INSTANCE: A graph G = (V,E), a positive integer K.

QUESTION: Does G have a coloring whose sum is <= K?

Let the vertices of a graph G be colored with k colors, i.e. let f: V --> {1,2,...,k}, such that for every pair uv of adjacent vertices, f(u) does not equal f(v). The sum of this coloring is the sum of values f(u) over all u in V, which we will denote SUM(f). The minimum values of SUM(f) over all proper colorings of G is called the chromatic sum of G. Schwenk and Kubicka have demonstrated the NP-completeness of CHROMATIC SUM and have constructed a polynomial algorithm for determining the chromatic sum of an arbitrary tree T. However, as far as I know no other chromatic sum algorithm exists, for any class of graphs. [E. Kubicka, The chromatic sum and efficient tree algorithms, Ph.D. Dissertation, Western Michigan University, 1989] [E. Kubicka and A. Schwenk, Introduction to chromatic sums, Proc. Seventh Ann. Computer Science Conf., 1989, pp. 39-45]

INSTANCE: A graph G = (V,E) with |V| <= 12, a positive integer K.

QUESTION: Does G have a k-coloring?

Obviously the decision problem corresponding to the problem of computing the chromatic number of a graph is NP-complete. Ron Read asks, however, is there an effective algorithm for computing the chromatic number of relatively small graphs? No such algorithm is known.

Read asks the same question concerning the problem of determining the edge chromatic number of small graphs.

INSTANCE: An Erdös graph G = (V,E) of index n.

QUESTION: Can G be colored with n colors?

Definition. An Erdös graph of index n is any graph which can be constructed from n copies of the complete graph K_n on n vertices by disjoint unions and vertex identifications, subject to the constraint that no two K_n's can have an edge in common. Imagine starting with n disjoint copies of K_n. You construct an Erdös graph of index n by executing the following simple algorithm:

Let G = K_n.

For i = 2 to n do

Select an arbitrary subset R of k vertices in the ith copy of K_n, for any k, 0 <= k <= (i-1).

Select an independent set S of k vertices in G.

Identify the vertices in R 1-1 with the vertices in S. (* Note that if k = 0, then essentially we add a disjoint copy of K_n to G. *) Let G be the new graph so constructed.

Erdös asks whether every graph so constructed has chromatic number equal to n. Note that every such graph contains a K_n as a subgraph, and hence the chromatic number of every Erdös graph is at least n. Erdös offered $500 for a solution to this lovely problem.

INSTANCE: A uniquely 4-colorable planar graph G = (V,E).

QUESTION: Can G be constructed from a planar embedding of K₄ by repeatedly placing a new vertex w inside a triangular face F and joing w to each of the three vertices of F?

This is an old problem, independently rediscovered by several people. I first thought of it around 1967, but others may have preceded me. The question really is: can all uniquely 4-colorable planar graph be constructed in this way? A graph G is uniquely 4-colorable if it can be colored with 4 colors, but every 4-coloring of G produces the same partition of the vertex set into 4 color classes.

INSTANCE: A product graph G = G₁ X G₂.

QUESTION: Can G be colored with <= K colors, where K is the smaller of the chromatic number of G₁ and the chromatic number of G₂?

By the product G X H of two graphs we mean the graph whose vertex set is the cartesian product of the vertex sets of G and H, and such that vertices (u,v) and (w,x) are adjacent in GXH if and only if u and w are adjacent in G and v and x are adjacent in H. This apparently is an extremely difficult problem to settle. It is known that if the minimum of the two chromatic numbers of G₁ and G₂ is <= 4, then the answer is 'yes'.

INSTANCE: A Pk-free graph G = (V,E).

QUESTION: Is there an effective on-line coloring algorithm for G?

graphs), P3-free graphs (i.e. disjoint unions of complete graphs), and P4-free graphs (i.e. cographs). Does the Gyarfas and Lehel result generalize to Pn-free graphs?