For those not familiar:

K-Coloring is the property that a graph can be colored with k colors such that no two neighboring nodes get the same color. The K-Coloring problem is a decision problem, ie a yes/no question.

The chromatic number of a graph is the lowest k for which it has a k-coloring.

Clearly, if you have an algorithm for one, you have an algorithm for the other.

The question was: is it faster to compute k-coloring than to compute its lowest (actual) k, ie its chromatic number.

Forests, trees, and bipartite graphs are 2-colorable. Planar graphs are 4-colorable. It is NP-complete to check if the chromatic number of a planar graph is 3.

There's a very interesting open problem, Hadwiger's conjecture that essentially says that the chromatic number is the clique (minor) number (whatever that means).

> Forests, trees, and bipartite graphs are 2-colorable.

More precise: a graph is bipartite if and only if it is 2-colorable (this can actually be used as a definition).

Since forests are bipartite, and trees are forests, the other two statements follow.