# What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not

Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not.

For example, consider the following two trees:

Example trees T and U are isomorphic.
An isomorphism (bijection) is described in the table below:

  T          U
1          2
2          4
3          1
4          5
5          3
"white"    "green"
"blue"     "white"


Below are some things to know about the problem:

• Nodes are colored
• edges are not colored.
• Nodes are free to be any color. Adjacent nodes are allowed to be the same color.
• which node is the root node of each tree cannot be changed.
• children are un-ordered.
• the tree is not necessarily a binary tree. a node could have 3 children, 4 children, 5, etc...

Formally, a colored tree is a tuple (VS, ES, root, color_set, color_map) such that:

• VS is the vertex set
• ES is the edge set
• (VS, ES) is a undirected tree
• root is a element of VS
• color_set is a set of objects called "colors"
• color_map is a mapping from VS to color_set
• every element of color_set appears in the range of color_map at least once. That is, every color is applied to at least one node.

colored trees T and U are isomorphic if and only if there exists a bijection, PHI from the vertex set of T, VT, to the vertex set of U, VU such that:

• the root of one tree is matched to the root of the other tree
• for all nodes v, w in VT, {v, w} is an edge in tree T if and only if {PHI(v), PHI(w)} is an edge in tree U
• for all nodes v, w in VT, v and w are the same color in tree T if and only if PHI(v), PHI(w) are the same color in tree U
• Do you know how to solve this without the colors? That would be a good start. – Yuval Filmus Jun 15 '19 at 14:24