Path coloring
Encyclopedia
In graph theory
, path coloring usually refers to one of two problems:
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
.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, path coloring usually refers to one of two problems:
- The problem of coloring a (multi)setMultisetIn mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
of pathsPath (graph theory)In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
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 coloringGraph coloringIn graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
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)setMultisetIn mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
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, digraphDirected graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
or multigraph
Multigraph
In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, , that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge....
.
External links
- http://citeseer.ist.psu.edu/erlebach00complexity.html The Complexity of Path Coloring and Call Scheduling by Thomas Erlebach and Klaus Jansen
- http://www.nada.kth.se/~viggo/wwwcompendium/node122.html A compendium of NP optimization problems by Viggo Kann (problem: Minimum Path Coloring)