In graph theory, path coloring usually refers to one of two problems:
- The problem of coloring a (multi)set of paths in graph, in such a way that any two paths of which share an edge in receive different colors. Set and graph are provided at input. This formulation is equivalent to vertex coloring the conflict graph of set, i.e. a graph with vertex set and edges connecting all pairs of paths of which are not edge-disjoint with respect to .
- The problem of coloring (in accordance with the above definition) any chosen (multi)set of paths in, such that the set of pairs of end-vertices of paths from is equal to some set or multiset, called a set of requests. Set and graph 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, may be a simple graph, digraph or multigraph.
Famous quotes containing the word path:
“Another danger is imminent: A contested result. And we have no such means for its decision as ought to be provided by law. This must be attended to hereafter.... If a contest comes now it may lead to a conflict of arms. I can only try to do my duty to my countrymen in that case. I shall let no personal ambition turn me from the path of duty. Bloodshed and civil war must be averted if possible. If forced to fight, I have no fears from lack of courage or firmness.”
—Rutherford Birchard Hayes (1822–1893)