Chromatic Number of Trees

$\begingroup$

All trees with more than one vertex have the same chromatic number. What is it & Why?

(Is this chromatic number by any chance 2, by definition of what a tree is? Since a tree is acyclic and connected, I think it would have a chromatic number that is strictly one less than 3, which is what a cycle would have to have)

$\endgroup$

1 Answer

$\begingroup$

Trees are bipartite graphs so you can always color them properly with two colors.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy