Adding an orientation to a given colored graph

Question

I am writing my master thesis on double round robin tournament planning.

Part of my solution model is to add home/away-patterns to a fixed tournament plan. This plan is an edge coloring with the color indicating the round, and the edge indicating the match between two teams (vertices). In each round, every team must play, so the graph is a complete graph. The orientation to be added indicates which of the two teams plays a home game. The interesting constraint is, that no team is allowed to play home or away three matches in a row.

So, formally, I reckon the problem is something like: (and I am not an expert on defining problems)

Given a colored graph (with an ordered coloring), add an orientation to each edge, such that for each vertex, no three edges with adjacent colors are assigned the same orientation.

I have made an algorithm, which I have tested on a few instances and it has not failed to solve the problem yet. However, I cannot prove that it works. In addition, I cannot find any of these types of problems and thereby some proven ways to solve it.

My question is: Is this a standard problem, or is there an equivalent problem? And is there a nice way to solve it?

(And is 'an ordered coloring' just mumbo-jumbo-nonsense?)

Answer 1

An ordered coloring is not mumbo-jumbo nonsense, but it is also not standard terminology. You could explain it, but personally I'd formalize your problem without colorings, as follows:

Our graph $G$ (or possibly multigraph, if two teams can play each other more than once) is the union of $k$ perfect matchings $M_1, M_2, \dots, M_k$ on the same set of $n$ vertices. (That is, each $M_i$ consists of $\frac n2$ edges that don't share any endpoints: it represents the games played in the $i^{\text{th}}$ round.) Our goal is to orient the edges of $M_1, \dots, M_k$ such that for each $1 \le i \le k-2$ and for each vertex $v$, both the out-degree and the in-degree of $v$ in $M_i \cup M_{i+1} \cup M_{i+2}$ are at least $1$.

In general, this topic is related to balanced orientations or almost-balanced orientations of graphs. See, for example, this question, where it is shown that any graph can be oriented so that the in-degree and out-degree of each vertex differ by at most $1$.

We could apply this to show that for each $i$, $M_i \cup M_{i+1} \cup M_{i+2}$ can be oriented in a way that satisfies this condition. However, doing this could land us in hot water: we also want $M_{i+1} \cup M_{i+2} \cup M_{i+3}$ to be oriented in this way, and the decisions we made for $M_{i+1}$ and $M_{i+2}$ without looking at $M_{i+3}$ might make this impossible.

Instead, here is a simple algorithm that is guaranteed to work: look at each of $M_1 \cup M_2$, $M_3 \cup M_4$, $M_5 \cup M_6$, and so on. Each of these $M_{2i-1} \cup M_{2i}$ is the union of two perfect matchings, so every vertex has degree $2$ in $M_{2i-1} \cup M_{2i}$. A graph in which every vertex has degree $2$ is either one big cycle or the union of multiple smaller cycles. In both cases, we can orient the edges around each cycle so that each vertex has in-degree $1$ and out-degree $1$.

This orientation is the home/away solution we're looking for! It has the following property: for every team, match $2i-1$ and match $2i$ involve playing one home game and one away game, in some order. Every block of three consecutive matches will contain an odd-numbered match followed by an even-numbered match, so it's impossible for a team to play three consecutive home games or three consecutive away games.