The oriented chromatic number of a directed graph G is the minimum order of an oriented graph to which G has a homomorphism. The oriented chromatic number χo(F) of a graph family F is the maximum oriented chromatic number over any orientation of any graph in F. For the family of hexagonal grids H2, Bielak (2006) proved that 5≤χo(H2)≤6. Here we close the gap by showing that χo(H2)≥6.

Discrete tomography deals with reconstructing finite spatial objects from their projections. The objects we study in this paper are called tilings or tile-packings, and they consist of a number of disjoint copies of a fixed tile, where a tile is defined as a connected set of grid points. A row projection specifies how many grid points are covered by tiles in a given row; column projections are defined analogously. For a fixed tile, is it possible to reconstruct its tilings from their projections in polynomial time? It is known that the answer to this question is affirmative if the tile is a bar (its width or height is 1), while for some other types of tiles $\mathbb {NP}$ -hardness results have been shown in the literature. In this paper we present a complete solution to this question by showing that the problem remains $\mathbb {NP}$ -hard for all tiles other than bars.

The optimal transformation of one tree into another by means of elementary edit operations is an important algorithmic problem that has several interesting applications to computational biology. Here we introduce a constrained form of this problem in which a partial mapping of a set of nodes (the "seeds") in one tree to a corresponding set of nodes in the other tree is given, and present efficient algorithms for both ordered and unordered trees. Whereas ordered tree matching based on seeded nodes has applications in pattern matching of RNA structures, unordered tree matching based on seeded nodes has applications in co-speciation and phylogeny reconciliation. The latter involves the solution of the planar tanglegram layout problem, for which a polynomial-time algorithm is given here.

Motivated by the question of the relative complexities of the graph isomorphism and the graph automorphism problems, we define and study the modular graph automorphism problems. These are the decision problems mod k -GA which consist, for each k > 1, of deciding whether the number of automorphisms of a graph is divisible by k. The mod k -GA problems all turn out to be intermediate in difficulty between graph automorphism and graph isomorphism. We define an appropriate search problem corresponding to mod k -GA and design an algorithm that polynomial-time reduces the mod k -GA search problem to the decision problem. Combining this algorithm with an IP protocol, we obtain a randomized polynomial-time checker for mod$_{k}$-GA $\forall k>1$.