Film Festival, with intersections graphs

Question

I encourage you to read this problem. I have a doubt, have films 1 and 2 the same type? I read the problem and I think that films {1,3,5}, {2,4,6}, {3,4} and {5,6} are grouped, but not is the case with fims 1 and 2, thus my answer is : 6 hours. Are you agree?

In a film festival competing six movies on opening day. Films 1, 3 and 5 are dramas, films 2, 4 and 6 are comedies, films 3 and 4 are independent, while the films 5 and 6 are of Hollywood. Each film lasts two hours. What is the minimum number of hours required to project all the films so that the films of the same type do not overlap?

Answer 1

You can indeed model this problem as a vertex colouring problem.

Every vertex in $G$ represents a film, and an edge between vertices $u$ and $v$ represents the fact that the films are of the same type. The objective is to find the minimal number of colours necessary for ensuring that no two adjacent vertices have the same colour. This minimum is called the chromatic number of $G$, usually denoted $\chi(G)$.

Finding $\chi(G)$ is an NP-complete problem, meaning no efficient algorithms are known to exist for it. There are, however, some useful results that provide upper bounds on $\chi(G)$:

1. Brooks' theorem: $\chi(G) \leq\Delta(G)$, unless the graph is complete or an odd cycle, in which case $\Delta(G) +1$ colours are required. (Here, $\Delta(G)$ denotes the maximum vertex degree of $G$.)
2. The four colour theorem: for any planar graph $G$, $\chi(G) \leq 4$. (A planar graph is any graph that can be embedded such that no two edges cross.)

Your graph $G$ is neither an odd cycle nor a complete graph, so $(1)$ guarantees you that $\chi(G) \leq \Delta(G) = 3$. Moreover, since you have at least one triangle in your graph, you know that $\chi(G) \geq 3$. Thus you can conclude that $\chi(G) = 3$ without trying any particular assignments.

Next, suppose that you were to vastly extend $G$ in such a way that you have some very high degree vertices, while keeping $G$ planar. Then $(2)$ provides you with a tighter bound on $\chi(G)$ than $(1)$, namely $\chi(G) \leq 4$. In addition, should you also find a $K_4$ subgraph in your new huge graph ($K_4$ is the one on the left), then you will already need 4 colours for this subgraph alone. So again, you will be able to conclude that $\chi(G) = 4$ without even trying any particular colour assignments.

These are two examples of heuristics you could use in solving this problem generally.