Discussion 5.20.
Everyone agrees that the graph \(\bfG\) in Figure 5.19 has chromatic number at most \(5\text{.}\) However, there’s a bit of debate going on about if \(\chi(\bfG)=5\text{.}\) Bob figures the authors would not have used five colors if they didn’t need to. Carlos says he’s glad they’re having the discussion, since all having a proper coloring does is provide them with an upper bound on \(\chi(\bfG)\text{.}\) Bob sees that the graph has a vertex of degree \(5\) and claims that must mean \(\chi(\bfG)=5\text{.}\) Alice groans and draws a graph with \(101\) vertices, one of which has degree \(100\text{,}\) but with chromatic number \(2\text{.}\) Bob is shocked, but agrees with her. Xing wonders if the fact that the graph does not contain a \(\bfK_3\) has any bearing on the chromatic number. Dave’s in a hurry to get to the gym, but on his way out the door he says they can get a proper \(4\)-coloring pretty easily, so \(\chi(\bfG)\leq 4\text{.}\) The rest decide it’s time to keep reading.
- What graph did Alice draw that shocked Bob?
- What changes did Dave make to the coloring in Figure 5.19 to get a proper coloring using four colors?