Hey everyone,

I recently learned about basic graph theory (BFS/DFS), and I would like to know approaches to the following two problems. I will discuss my thoughts after I present the problems.

1) Given an undirected graph $$$G = (V, E)$$$ whose $$$V$$$ vertices are colored with at most $$$V$$$ distinct colors, how can I determine whether there exist two vertices $$$u$$$ and $$$v$$$ with $$$d(u, v) \leq 2$$$ such that the color of $$$u$$$ is equal to the color of $$$v$$$?

This problem seems really similar to the bipartite coloring problem, but the key differences are that we're allowed to use up to $$$n$$$ colors, and we need to make sure that no two vertices have the same color within a distance of two. I thought about this problem for a while, and I couldn't come up with too much. I thought about somehow "augmenting" each node with the colors of its adjacent vertices, but I couldn't really get much from there. I'm not sure if this is the right direction or not.

2) Given a DAG $$$G = (V, E)$$$ with each vertex colored with colors $$$1$$$, $$$2$$$, or $$$3$$$, how can I find the set of all vertices colored $$$1$$$ that are reachable from both a vertex with color $$$2$$$ AND a vertex with color $$$3$$$?

So when I see DAG, I usually think of topological sort. But I really can't get anywhere with this problem. I thought about reversing the edges and performing a depth-first search from each of the vertices colored $$$1$$$, but this would be $$$O(V(V + E))$$$ in the worst case, and I'm pretty sure we can do better.

Could someone please help me with these graph theory problems? Thank you