First Lower Bound
Finding A Lower Bound
A First Attempt
A fairly obvious way to attempt a coloring proceeds as follows:
-
First select
, the only independent set of size 7,
and color its vertices with color1.
-
Then we can try to find an independent set of size 6
(did you find such a set disjoint from
?) and color those vertices
using color2.
-
We can use the next color, say color3, for the largest independent set composed of
vertices that have not yet been assigned a color.
Problem
31:
Continue this way. See how far you can go.
|