Understanding some facts about complete graph

81 Views Asked by At

I read following fact:

Uniquely colorable graph is a graph in which each vertex of chromatic partition has different color.

Does that mean:

  1. "Only" complete graphs are uniquely colorable?

Also have following doubts not related to graph coloring:

  1. Does the independent set of complete graph contain single vertex?
1

There are 1 best solutions below

4
On BEST ANSWER

Your sentence is not well written, it should be

A uniquely colorable graph is a graph in which all sets in a chromatic partition have different colors.

The complete graph is trivially uniquely colorable, but this in not an equivalence. Any tree is uniquely $2$-colorable for instance. Even cycles are uniquely $2$-colorable too. Odd cycles are not uniquely $3$-colorable though.

Does the independent set of complete graph contain single vertex?

Yes. The unique independent sets of a complete graph are made of single vertices.