Time to learn something!
1. Go to Wikipedia.
2. Click on "Random article" in the left-hand sidebar box.
3. Post it!
File this under "I was absent the day we did New Math":
In graph theory, path coloring usually refers to one of two problems:
- The problem of coloring a (multi)set of paths R in graph G, in such a way that any two paths of R which share an edge in G receive different colors. Set R and graph G are provided at input. This formulation is equivalent to vertex coloring the conflict graph of set R, i.e. a graph with vertex set R and edges connecting all pairs of paths of R which are not edge-disjoint with respect to G.
- The problem of coloring (in accordance with the above definition) any chosen (multi)set R of paths in G, such that the set of pairs of end-vertices of paths from R is equal to some (multi)set I, called a set of requests. Set I and graph G are provided at input. This problem is a special case of a more general class of graph routing problems, known as call scheduling.
In both the above problems, the goal is usually to minimise the number of colors used in the coloring. In different variants of path coloring, G may be a simple graph, digraph or multigraph.
Wake up! It's over! I promise!
I tried to learn from your post. I swear. Really. That was a double espresso moment. Maybe I should have Drew explain it to me. He taught me all about G-force ealier this week - on 6 hours sleep. Twerp.
Posted by: leah | September 13, 2006 at 09:25 PM