Abstract. We obtain lower and upper bounds for the maximum weight of a directed cut in the classes of weighted digraphs and weighted acyclic digraphs as well as in some of their subclasses. We compare our results with those obtained for the maximum size of a directed cut in unweighted digraphs. In particular, we show that a lower bound obtained by Alon, Bollobás, Gyárfás, Lehel, and Scott [ J. Graph Theory, 55 (2007), pp. 1–13] for unweighted acyclic digraphs can be extended to weighted digraphs with the maximum length of a cycle being bounded by a constant and the weight of every arc being at least one. We state a number of open problems.

In this article, we consider a stochastic variant of the so-called Santa Claus problem. The Santa Claus problem is equivalent to the problem of scheduling a set of n jobs on m parallel machines without preemption, so as to maximize the minimum load. We consider the identical machine version of this scheduling problem with the additional restriction that the scheduler has only a guess of the processing times; that is, the processing time of a job is a random variable . We show that there is a critical value ρ ( n,m ) such that if the duration of the jobs is exponentially distributed and the expected values deviate by less than a multiplicative factor of ρ ( n,m ) from each other, then a greedy algorithm has an expected competitive ratio arbitrarily close to one; that is, it performs in expectation almost as good as an algorithm that knows the actual values in advance . On the other hand, if the expected values deviate by more than a multiplicative factor of ρ ( n,m ), then the expected performance is arbitrarily bad for all algorithms.

Consider words over an alphabet with n letters. Fisher [Amer. Math. Monthly, 96 (1989), pp. 610–614] calculated the number of distinct words of length $\ell$ assuming certain pairs of letters commute. In this paper we are interested in a more general setting where the pairs of letters that commute at a certain position of a word depend on the initial segment of the word. In particular, we show that if for each word at each position any letter fails to commute with at most a constant number of other letters, then the number of distinct words of length $\ell$ is at most $C^{n+\ell}$ for some constant C. We use this result to obtain a lower bound on the number of diagonal flips required in the worst case to transform one n-vertex labeled triangulated planar graph into some other one. This has previously been proved in [D. D. Sleator, R. E. Tarjan, and W. P. Thurston, SIAM J. Discrete Math., 5 (1992), pp. 428–450] by different methods.

We are interested in a version of graph coloring where there is a "co-site" constraint value k. Given a graph G with a nonnegative integral demand x v at each node v, we must assign x v positive integers (colors) to each node v such that the same integer is never assigned to adjacent nodes, and two distinct integers assigned to a single node differ by at least k. The aim is to minimize the span, that is, the largest integer assigned to a node. This problem is motivated by radio channel assignment where one has to assign frequencies to transmitters so as to avoid interference. We compare the span with a clique-based lower bound when some of the demands are large. We introduce the relevant graph invariant, the k-imperfection ratio, give equivalent definitions, and investigate some of its properties. The k-imperfection ratio is always at least 1: we call a graph k-perfect when it equals 1. Then 1-perfect is the same as perfect, and we see that for many classes of perfect graphs, each graph in the class is k-perfect for all k. These classes include bipartite graphs and more generally comparability graphs, co-comparability graphs, and line-graphs of bipartite graphs.