Graph with no 3-clique that needs at least 4 colors

0 votes

Give an example of a graph that has the following properties.  (Note that you need to give a single graph as the answer.)

  1. The graph does not contain a triangle (that is, a clique of 3 vertices) as a subgraph.
  2. Graph needs at least 4 colors for a proper vertex coloring

[If you think that such a graph is not possible, then prove that statement.]

asked Jul 24 in Graph Theory by Amrinder Arora (38 points)

Please log in or register to answer this question.

The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc