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 different 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