In tournament schedules, a break occurs when a team plays two consecutive home or two consecutive away games. Minimizing breaks is important for ensuring competitive fairness and logistical efficiency. This article addresses the problem of minimizing breaks in incomplete round-robin schedules in which each pair of teams plays again each other at most once. The problem of minimizing breaks is a classical problem that was previously thoroughly studied in the context of complete round-robin schedules. Using a graph-theoretic model we analyze structural properties of incomplete round-robin schedules. We derive some bounds on the minimum number of breaks. Then, we propose an algorithm that is able to construct incomplete single round-robin schedules minimizing the number of breaks for given numbers of teams and rounds if the number of rounds is not larger than 3 / 4 of the number of teams.

In round-robin schedules, a break occurs when a team plays two consecutive home or two consecutive away games. Minimizing breaks is important for ensuring competitive fairness and logistical efficiency. This article addresses the problem of minimizing breaks in incomplete round-robin schedules in which each pair of teams plays again each other at most once. The problem of minimizing breaks is a classical problem that was previously thoroughly studied in the context of complete round-robin schedules. Using a graph-theoretic model we analyze structural properties of incomplete round-robin schedules. We derive some bounds on the minimum number of breaks. Then, we propose an algorithm that is able to construct incomplete single round-robin schedules minimizing the number of breaks for given numbers of teams and rounds if the number of rounds is not larger than 3/4 of the number of teams.

The exploration of one-factorizations of complete graphs is the foundation of some classical sports scheduling problems. One has to traverse the landscape of such one-factorizations by moving from one of those to a so-called neighbor one-factorization. This approach amounts to modifying locally the coloring associated with a one-factorization. We consider some particular types of modifications and describe various constructions which give one-factorizations which may be modified or not by these techniques. Among those are recoloring of bichromatic cycles, altering of optimally colored subcliques of even size, or recoloring of chordless lanterns.

Abstract An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph G = (V,E) and a family $\cal {P}$ of chains Pi together with vectors h(Pi) = (h ,…,h ), one wants to find a partition V1,…,Vk of V such that for each Pi and each color j, |Vj ∩ Pi| = h . An interpretation in terms of scheduling is presented. We consider special cases of graphs and identify polynomially solvable cases; general complexity results are established in this case and also in the case where V1,…,Vk is required to be a proper vertex k‐coloring of G. Finally, we examine also the case of (proper) edge k‐colorings and determine its complexity status. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008

Abstract Starting from the trivial observation that, in any optimal coloring of a graph, there always exists a node v such that its neighborhood N(v) contains all colors, we examine related properties in suboptimal colorings (i.e., those using more than χ(G) colors, where χ(G) is the chromatic number). In particular, we show that, in any (χ(G) + p)‐coloring of G, there is a node v such that its generalized neighborhood Nq(v) with q = max{2p − 1, 2} contains χ(G) colors for p ≥ 1. Additional properties of (χ(G) + p)‐colorings are also given. © 2004 Wiley Periodicals, Inc.

Abstract A graph‐theoretical model is presented for scheduling the transmission of messages in a computer network. A related wiring problem is also discussed; connections with classical edge colorings are exhibited and optimality properties are discussed. © 1993 by John Wiley & Sons, Inc.

Abstract Variations and extensions of the Open‐Shop Scheduling Problem are presented with an emphasis on models suitable for some automated production systems. Complexity results are given and polynomially solvable cases are described. © 1993 by John Wiley & Sons, Inc.

An edge-coloring model for some types of scheduling problems is described; the case is handled where some collections of (nonadjacent) edges are required to have the same color. This corresponds to simultaneity constraints. The complexity of this problem is studied. Next, some classes of graphs for which such colorings exist are characterized, and a recognition algorithm is derived.

An edge coloring model is described for dealing with a special type of cyclic scheduling problem: each edge e of a graph has an integral weight $p_e \geqq 0$. An interval cyclic edge T-coloring is an assignment of $p_e $ cyclically consecutive colors in $\{ 1, \cdots ,T \}$ to each edge e such that no two adjacent edges share a common color and, for each bundle (collection of edges adjacent to a same node) or triangle A, all colors used on edges of A are cyclically consecutive. Let $T( p,G ) = \max _A \{ \Sigma p_e :e \in A:A\,{\text{is a bundle or a triangle}} \}$. A graph G is called ice-perfect if, for any assignment p of values $p_e $ to the edges, there exists an interval cyclic edge $T( p,G )$-coloring. We show that a graph is ice-perfect if and only if it is a triangle or a bipartite outerplanar graph. Applications to scheduling in flexible manufacturing systems are mentioned.

Abstract Some variations on Eulerian partitions of edge sets and arc sets are discussed. We consider partitions into (odd) paths, chains and antipaths; these are paths where every second are is reversed. Packing problems are also examined and min‐max results are derived by using network flow techniques.

When an injective pseudo-Boolean function $f:B^n \to \mathbb{R}$ is minimized, where $B^n = \{ 0,1 \}^n$ is the set of vertices of the unit-hypercube, it is natural to consider so-called greedy vertex-following algorithms. These algorithms construct a sequence of neighbouring (Hamming distance 1) vertices with decreasing f-value. The question arises as to when such algorithms will find the global optimum given any starting point. This paper describes a hierarchy of such classes of functions that are shown to strictly contain each other. These classes are, in increasing order of generality, the threshold, the saddle-free, the pseudomodular, the completely unimodal, the unimodal, and the unimin (respectively, unimax) functions. Some considerations as to the complexity of the above-mentioned class of algorithms are also made.

Abstract The construction of schedules for a sports league reduces to finding a factorization of a complete graph. In the case where all games are played in the home city of one of the teams, one can represent schedules by means of oriented edge colorings. In this article we consider the case where the league consists of several divisions of equal size; constructions are described which take into account requirements concerning the breaks in the alternating sequences of home and away games as well as the consecutive arrangements of games inside a division or between divisions.

Abstract Given a multigraph G, a sequence (h1,…, hm) of nonnegative integers h1 ≥… ≥ hm is color‐feasible for G if there is an edge‐coloring H1,…, Hm where Hi has exactly hi edges (i=1,…, m). It is known that the set C(G) of color‐feasible sequences of G is partially ordered. We show that if G is simple with maximum degree d, then all maximal sequences of C(G) have at most d+1 nonzero entries. This result can be extended to multigraphs. Furthermore, if the odd elementary cycles of a multigraph G satisfy some specified conditions then all maximal sequences have at most d+1 nonzero entries.