Question

Problem 12.29. A basic example of a simple graph with chromatic number n is the complete graph on n vertices, that is x(Kn) n. This implies that any graph with Kn as a subgraph must have chromatic number at least n. It's a common misconception to think that, conversely, graphs with high chromatic number must contain a large complete sub- graph. In this problem we exhibit a simple example countering this misconception, namely a graph with chromatic number four that contains no triangle-length three cycle rand hence no subgraph isomorphic to Kn for n 3. Namely, let G be the 11-vertex graph of Figure 12.27. The reader can verify that G is triangle-free. Figure 12.27 Graph G with no triangles and x(G)4 (a) Show that G is 4-colorable. (b) Prove that G can't be colored with 3 colors.

Answer 1

For any doubt

Comment

Letelauno be blue, green bhet. but it Colounng.wwoL