## Description

1. Let G be a color graph where each node has a color and multiple nodes

can share the same color. In particular, there is a designated initial node.

An ω-path is an infinite walk on G that starts from the initial.

(1). Design an algorithm that decides where there is an ω-path on which

✷(yellow ∨ ✸blue) holds.

(2). Design an algorithm that decides where there is an ω-path on which

✷✸(yellow ∨ ✸blue) holds.

2. Let G be a color graph where each node has a color and multiple nodes

can share the same color. In particular, there is a designated initial node.

An ω-path is an infinite walk on G that starts from the initial. Design an

algoirthm to decide whether there is an ω-path on which it passes red nodes

for infinitely many times and passes blue nodes for only finitely many times.

3. Let G be a color graph where each node has a color and multiple nodes

can share the same color. In particular, there is a designated initial node.

An ω-path is an infinite walk on G that starts from the initial. A good ωpath is is one where there are infinitely many prefixes, each of which satisfies

the following condition: the number of red nodes equals the number of blue

nodes. Design an algoirthm to decide whether there is a good ω-path.

4. Let G be a color graph where each node has a color and multiple nodes

can share the same color. In particular, there is a designated initial node.

An ω-path is an infinite walk on G that starts from the initial. A bad ω-path

is is one where there are infinitely many prefixes, each of which satisfies the

following condition: the number of red nodes is a multiple of 5. Design an

algoirthm to decide whether there is a bad ω-path.