0
$\begingroup$

Suppose that I have a tree where each node is either of type A or type B.

Nodes of type A have outgoing edges only to nodes of type B and vice versa.

Is there a name/term for this kind of a tree?

A concrete example of such a tree would be the state tree of a 2 player game (like tic-tac-toe) which has alternating levels of states where it's X's turn or Y's turn.

$\endgroup$
  • $\begingroup$ In computing model, there is an ATM (Alternative Turing machine) which has some similarity to the above definition of the tree. In this model, every node has either existential type or universal. The machine has no transition rule between nodes with the same type. $\endgroup$ – Doralisa Dec 16 '18 at 16:44
1
$\begingroup$

Such a tree would be 2-colored.

Note that all trees are 2-colorable; a 2-colored tree is just one where the coloring's already happened.

$\endgroup$
  • $\begingroup$ Sadly this term isn't extendable to more than 2 alternating types (e.g. nodes of type A connected to those of type B connected to those of type C connected to those of type A) $\endgroup$ – Peeyush Kushwaha Oct 17 '18 at 5:15
0
$\begingroup$

All trees (and forests) can be 2-colored. However there are even additional kinds (e.g. with balancing conditions).

Is every acyclic graph 2-colorable?

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.