Recap: What is a chromatic number x(G) and what is a k-coloring?
Recap:
What is a:
Clique
Clique number
clique parition
Show it with this pic:
Ex.: 1 Colorings and Planarity
Recap: What is here the number of vertices in a maximim size independent set of G: alpha(G)
Recap: when is a graph called planar?
Optimal: yes because the clique has 6 vertices and at least 6 colours
c) The fifth workshop platform only has one repair job assigned to it, namely job 7. As this job has a profit of only 90e, the owner should refuse this job.
With the current assignments, all other platforms are profitable.
Ex: 4 (Greed Edge Colorings)
is it optimal?
Last changeda year ago
