First Lower Bound
Finding A Lower Bound
A First Attempt
At this point, we can already establish some kind of lower bound for the number of colors needed:
Every coloring of the graph G must use at least 13 colors.
|
Proof
Since the size of every independent set is at most 7, the number of colors used by
any coloring must be at least
Equation
14
|